Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor

DOI10.1007/978-3-642-11269-0_20zbMath1273.05221OpenAlexW1550062525MaRDI QIDQ3656866

Shai Gutner

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_20

zbMATH Keywords

dominating set problemproblem kernelfixed-parameter tractable algorithms\(H\)-minor-free graphsdegenerated graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Unnamed Item ⋮ A linear kernel for a planar connected dominating set ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Twin-width and polynomial kernels ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• The extremal function for complete minors
• Parametrized complexity theory.
• Local tree-width, excluded minors, and approximation algorithms
• A refined search tree technique for dominating set on planar graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• An extremal function for contractions of graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• The complexity of finding maximum disjoint paths with length constraints
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Topological cliques in graphs II
• Automata, Languages and Programming
• SOFSEM 2006: Theory and Practice of Computer Science