Fixed parameter algorithms for Planar Dominating Set and related problems

DOI10.1007/3-540-44985-X_10MaRDI QIDQ2721971zbMATH OpenFDO

Authors Jochen Alber, Henning Fernau, Rolf Niedermeier, Hans L. Bodlaender

Publication date 11 July 2001

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

Full work available at URL https://doi.org/10.1007/3-540-44985-X_10

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

• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Improved parameterized algorithms for planar dominating set
• Mathematical Foundations of Computer Science 2004
• Parameterized approximation of dominating set problems
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Parameterized Algorithms for Generalized Domination
• Computational study on planar dominating set problem
• Computational Study on Dominating Set Problem of Planar Graphs
• Computational study for planar connected dominating set problem
• On the complexity of fixed parameter clique and dominating set

Cited in

(20)

• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• On the existence of subexponential parameterized algorithms
• Graph separators: A parameterized view
• A refined search tree technique for dominating set on planar graphs
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• A strengthened analysis of an algorithm for dominating set in planar graphs
• scientific article; zbMATH DE number 1320677 (Why is no real title available?)
• Small k-dominating sets in planar graphs with applications
• Subexponential parameterized algorithms
• Confronting intractability via parameters
• Refined search tree technique for DOMINATING SET on planar graphs
• A linear kernel for planar red-blue dominating set
• Mathematical Foundations of Computer Science 2004
• Dominating sets and local treewidth
• Reachability problems in interval-constrained and cardinality-constrained graphs
• An exact algorithm for connected red-blue dominating set
• On the complexity of fixed parameter clique and dominating set
• The tape reconfiguration problem and its consequences for dominating set reconfiguration
• Linear-time algorithms for problems on planar graphs with fixed disk dimension
• Dynamic programming and planarity: improved tree-decomposition based algorithms

This page was built for publication: Fixed parameter algorithms for Planar Dominating Set and related problems

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