Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

DOI10.1007/978-3-642-28050-4_21zbMath1352.68105OpenAlexW119394587MaRDI QIDQ2891355

Robert Ganian

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Structural parameterizations for boxicity ⋮ Between treewidth and clique-width ⋮ Target Set Selection in Dense Graph Classes ⋮ Kernelization using structural parameters on sparse graph classes ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Between Treewidth and Clique-Width ⋮ Structural parameterization of cluster deletion ⋮ Structural parameterization of alliance problems ⋮ Unnamed Item ⋮ Extended MSO model checking via small vertex integrity ⋮ Graph Motif Problems Parameterized by Dual ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Unnamed Item ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item ⋮ Imbalance parameterized by twin cover revisited ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Computing the chromatic number using graph decompositions via matrix rank

Cites Work

• Unnamed Item
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of some colorful problems parameterized by treewidth
• Improved upper bounds for vertex cover
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• A special planar satisfiability problem and a consequence of its NP- completeness
• Linear time solvable optimization problems on graphs of bounded clique-width
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• On the Kernelization Complexity of Colorful Motifs
• Parameterized Algorithms for Boxicity
• Clique-Width is NP-Complete
• Algorithmic Meta-theorems for Restrictions of Treewidth
• Graph Layout Problems Parameterized by Vertex Cover
• What Makes Equitable Connected Partition Easy
• Equitable Coloring