Computational study on planar dominating set problem

DOI10.1016/j.tcs.2009.04.012zbMath1192.68488OpenAlexW2025536756WikidataQ60402581 ScholiaQ60402581MaRDI QIDQ1040587

Qian-Ping Gu, Marjan Marzban, Xiao-Hua Jia

Publication date: 25 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.012

zbMATH Keywords

data reductioncomputational studyfixed-parameter algorithmsbranch-decompositionplanar dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

New analysis and computational study for the planar connected dominating set problem ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Computational study on a PTAS for planar dominating set problem

Uses Software

• LEDA
• TSPLIB
• PIGALE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Experiments on data reduction for optimal domination in networks
• Matrix multiplication via arithmetic progressions
• Graph minors. I. Excluding a forest
• Graph minors. X: Obstructions to tree-decomposition
• Approximation algorithms for combinatorial problems
• Call routing and the ratcatcher
• Experimental analysis of Heuristic algorithms for the dominating set problem
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Random sampling of large planar maps and convex polyhedra
• A threshold of ln n for approximating set cover
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• Polynomial-time data reduction for dominating set
• Graph minors. II. Algorithmic aspects of tree-width
• TSPLIB—A Traveling Salesman Problem Library
• Approximation algorithms for NP-complete problems on planar graphs
• Domination in Graphs Applied to Electric Power Networks
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms – ESA 2005
• Computational Study on Dominating Set Problem of Planar Graphs
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS

This page was built for publication: Computational study on planar dominating set problem