Computational Study on Dominating Set Problem of Planar Graphs

DOI10.1007/978-3-540-85097-7_9MaRDI QIDQ5505646zbMATH OpenOpenAlexWikidataFDO

Authors Marjan Marzban, Qian-Ping Gu, X.-H. Jia

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_9

zbMATH Keywords

branch-decompositioncomputational studydata reductionfixed-parameter algorithmsPLANAR DOMINATING SET

Mathematics Subject Classification ID

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

Recommendations

• Computational study on planar dominating set problem
• Computational study for planar connected dominating set problem
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• New analysis and computational study for the planar connected dominating set problem
• scientific article; zbMATH DE number 1929955

Cited in

(10)

• Computational study on planar dominating set problem
• Computational study on a PTAS for planar dominating set problem
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• A refined search tree technique for dominating set on planar graphs
• scientific article; zbMATH DE number 1617251 (Why is no real title available?)
• Computational study for planar connected dominating set problem
• Computational study on bidimensionality theory based algorithm for longest path problem
• New analysis and computational study for the planar connected dominating set problem
• A strengthened analysis of an algorithm for dominating set in planar graphs
• scientific article; zbMATH DE number 1834643 (Why is no real title available?)

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Computational Study on Dominating Set Problem of Planar Graphs

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