Computational Study on a PTAS for Planar Dominating Set Problem

Algorithms

Marjan Marzban¹ 

[1] School of Computing Science, Simon Fraser University, Burnaby BC, V5A 1S6, Canada; E-Mail

关键词: dominating set problem;    PTAS;    branch-decomposition based algorithms;    planar graphs;    computational study;   

DOI  :  10.3390/a6010043

来源: mdpi

【 摘 要 】

The dominating set problem is a core NP-hard problem in combinatorial optimization and graph theory, and has many important applications. Baker [JACM 41,1994] introduces a k-outer planar graph decomposition-based framework for designing polynomial time approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is mentioned that the framework can be applied to obtain antime. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.