Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

DOI10.1016/j.dam.2005.02.029zbMath1080.05093OpenAlexW2148989696MaRDI QIDQ2576350

Prabhakar Ragde, Naomi Nishimura, Dimitrios M. Thilikos

Publication date: 27 December 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.02.029

zbMATH Keywords

graph minorsparametrized complexityFPT algorithms

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the parameterized complexity of maximum degree contraction problem ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Sparse obstructions for minor-covering parameters ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Kernels for packing and covering problems ⋮ A classification for community discovery methods in complex networks ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Advice classes of parametrized tractability
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• The node-deletion problem for hereditary properties is NP-complete
• Quickly excluding a forest
• Upper bounds on the size of obstructions and intertwines
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• On search, decision, and the efficiency of polynomial-time algorithms
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On the agreement of many trees
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• On computing graph minor obstruction sets
• Algorithms and obstructions for linear-width and related search parameters
• Graph minors. XIII: The disjoint paths problem
• Disjoint Paths—A Survey
• Nonconstructive tools for proving polynomial-time decidability
• Nondeterminism within $P^ * $
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results