Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

DOI10.1007/978-3-540-73545-8_39MaRDI QIDQ3608864zbMATH OpenOpenAlexFDO

Authors Noga Alon, Shai Gutner

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

zbMATH Keywords

degenerated graphsdominating set problemfinding an induced cyclefixed-parameter tractable algorithmsH-minor-free graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

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

Cited in

(8)

• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Parameterized complexity of generalized domination problems
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Parameterized Algorithms for Generalized Domination
• scientific article; zbMATH DE number 7764102 (Why is no real title available?)
• 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)