Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
DOI10.1007/978-3-540-73545-8_39zbMATH Open1206.05073OpenAlexW2191175579MaRDI QIDQ3608864FDOQ3608864
Publication date: 6 March 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_39
Recommendations
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- scientific article; zbMATH DE number 1979505
dominating set problemfixed-parameter tractable algorithmsH-minor-free graphsdegenerated graphsfinding an induced cycle
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (7)
- Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
- Title not available (Why is that?)
- Parameterized complexity of generalized domination problems
- Parameterized Algorithms for Generalized Domination
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- The parameterized complexity of editing graphs for bounded degeneracy
This page was built for publication: Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608864)
