Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

DOI10.1007/978-3-642-04128-0_62zbMath1256.68084MaRDI QIDQ3639282

Somnath Sikdar, Geevarghese Philip, Venkatesh Raman

Publication date: 29 October 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-642-04128-0_62

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Lossy Kernels for Connected Dominating Set on Sparse Graphs, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, Unnamed Item, An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification, Lower bounds on kernelization, Confronting intractability via parameters, The kernelization complexity of connected domination in graphs with (no) small cycles, Dominating set is fixed parameter tractable in claw-free graphs, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, FPT algorithms for domination in sparse graphs and beyond, Reconfiguration on sparse graphs, Revising Johnson's table for the 21st century, Minimum fill-in of sparse graphs: kernelization and approximation, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, Hitting Forbidden Minors: Approximation and Kernelization, Domination When the Stars Are Out, Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs, Kernelization: New Upper and Lower Bound Techniques, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor