Computational study on planar dominating set problem

DOI10.1016/J.TCS.2009.04.012zbMATH Open1192.68488OpenAlexW2025536756WikidataQ60402581 ScholiaQ60402581MaRDI QIDQ1040587FDOQ1040587

Authors: Marjan Marzban, Qian-Ping Gu, X.-H. 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

Recommendations

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

zbMATH Keywords

data reductionfixed-parameter algorithmscomputational studybranch-decompositionplanar dominating set

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• Computational study on a PTAS for planar dominating set problem
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Computational Study on Dominating Set Problem of Planar Graphs
• New analysis and computational study for the planar connected dominating set problem
• Practical algorithms for branch-decompositions of planar graphs
• Computational study for planar connected dominating set problem

Uses Software

• LEDA
• TSPLIB
• PIGALE

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

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