Subexponential algorithms for partial cover problems

DOI10.4230/LIPICS.FSTTCS.2009.2318MaRDI QIDQ2920126zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh

Publication date 24 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_8f12.html

zbMATH Keywords

parameterized complexityirrelevant vertex techniquesubexponential time algorithmspartial cover problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Subexponential algorithms for partial cover problems
• Implicit branching and parameterized partial cover problems
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Cited in

(11)

• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• Algorithms for the minimum edge cover of \(H\)-subgraphs of a graph
• Implicit branching and parameterized partial cover problems
• Pareto complexity of two-parameter FPT problems: a case study for partial vertex cover
• Approximating subdense instances of covering problems
• Subexponential algorithms for partial cover problems
• Planar \(k\)-path in subexponential time and polynomial space
• Tight bounds on subexponential time approximation of set cover and related problems
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Implicit branching and parameterized partial cover problems (extended abstract)
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting

This page was built for publication: Subexponential algorithms for partial cover problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920126)