Subexponential algorithms for partial cover problems

DOI10.4230/LIPICS.FSTTCS.2009.2318zbMATH Open1248.68215OpenAlexW1589076819MaRDI QIDQ2920126FDOQ2920126

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

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

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)

Cited In (11)

• Title not available (Why is that?)
• 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
• Planar \(k\)-path in subexponential time and polynomial space
• Subexponential algorithms for partial cover problems
• 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)