Parameterized Complexity for Domination Problems on Degenerate Graphs
From MaRDI portal
Publication:5302055
DOI10.1007/978-3-540-92248-3_18zbMath1202.68278OpenAlexW1524652898MaRDI QIDQ5302055
Petr A. Golovach, Yngve Villanger
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_18
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (19)
Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ An approval-based model for single-step liquid democracy ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Unnamed Item ⋮ Implicit branching and parameterized partial cover problems ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ A Constructive Arboricity Approximation Scheme ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ Unnamed Item ⋮ Twin-width and polynomial kernels ⋮ Partial vertex cover on graphs of bounded degeneracy
Cites Work
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Perfect Code is \(W[1\)-complete]
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The extremal function for complete minors
- Parameterized complexity of Vertex Cover variants
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)
- An extremal function for contractions of graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Finding All Spanning Trees of Directed and Undirected Graphs
- How to Allocate Network Centers
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Partial vs. Complete Domination: t-Dominating Set
This page was built for publication: Parameterized Complexity for Domination Problems on Degenerate Graphs
