Computational study on a PTAS for planar dominating set problem

DOI10.3390/a6010043zbMath1461.68258OpenAlexW2039826584MaRDI QIDQ1736542

Marjan Marzban, Qian-Ping Gu

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a6010043

zbMATH Keywords

planar graphscomputational studyPTASdominating set problembranch-decomposition-based algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Editorial: Special issue on graph algorithms

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational study on planar dominating set problem
• 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
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• 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
• Polynomial-time data reduction for dominating set
• TSPLIB—A Traveling Salesman Problem Library
• Efficient Planarity Testing
• Approximation algorithms for NP-complete problems on planar graphs
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms - ESA 2003