Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

DOI10.1007/978-3-642-28050-4_21zbMath1352.68105MaRDI 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

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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