Improved parameterized algorithms for planar dominating set

DOI10.1007/3-540-45687-2_33MaRDI QIDQ4708588zbMATH OpenFDO

Authors Ljubomir Perković, Iyad Kanj

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200399.htm

zbMATH Keywords

NP-complete problemsparameterized algorithmsplanar dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Refined search tree technique for DOMINATING SET on planar graphs

Cited in

(23)

• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• On parameterized exponential time complexity
• Computational study on planar dominating set problem
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Computational study on a PTAS for planar dominating set problem
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Improved parameterized algorithms and kernels for mixed domination
• Kernels in planar digraphs
• A refined search tree technique for dominating set on planar graphs
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• Genus characterizes the complexity of certain graph problems: Some tight results
• Fixed parameter algorithms for Planar Dominating Set and related problems
• New upper bounds on the decomposability of planar graphs
• Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Subexponential parameterized algorithms
• Confronting intractability via parameters
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Mathematical Foundations of Computer Science 2004
• Computational Study on Dominating Set Problem of Planar Graphs
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Linearity of grid minors in treewidth with applications through bidimensionality

This page was built for publication: Improved parameterized algorithms for planar dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4708588)