Computational Study on a PTAS for Planar Dominating Set Problem
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-h...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2013-01-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/6/1/43 |
| _version_ | 1818114717469638656 |
|---|---|
| author | Qian-Ping Gu Marjan Marzban |
| author_facet | Qian-Ping Gu Marjan Marzban |
| author_sort | Qian-Ping Gu |
| collection | DOAJ |
| description | 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 an O(2ckn) time, c is a constant, (1+1/k)-approximation algorithm for the planar dominating set problem. We show that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. We modify the application of the framework to give a PTAS for the planar dominating set problem. With k-outer planar graph decompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer planar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k) in O(22ckn) time. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical. |
| first_indexed | 2024-12-11T03:55:10Z |
| format | Article |
| id | doaj.art-05fa9f793d734f728e795407d32f58bd |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-11T03:55:10Z |
| publishDate | 2013-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-05fa9f793d734f728e795407d32f58bd2022-12-22T01:21:48ZengMDPI AGAlgorithms1999-48932013-01-0161435910.3390/a6010043Computational Study on a PTAS for Planar Dominating Set ProblemQian-Ping GuMarjan MarzbanThe 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 an O(2ckn) time, c is a constant, (1+1/k)-approximation algorithm for the planar dominating set problem. We show that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. We modify the application of the framework to give a PTAS for the planar dominating set problem. With k-outer planar graph decompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer planar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k) in O(22ckn) time. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical.http://www.mdpi.com/1999-4893/6/1/43dominating set problemPTASbranch-decomposition based algorithmsplanar graphscomputational study |
| spellingShingle | Qian-Ping Gu Marjan Marzban Computational Study on a PTAS for Planar Dominating Set Problem Algorithms dominating set problem PTAS branch-decomposition based algorithms planar graphs computational study |
| title | Computational Study on a PTAS for Planar Dominating Set Problem |
| title_full | Computational Study on a PTAS for Planar Dominating Set Problem |
| title_fullStr | Computational Study on a PTAS for Planar Dominating Set Problem |
| title_full_unstemmed | Computational Study on a PTAS for Planar Dominating Set Problem |
| title_short | Computational Study on a PTAS for Planar Dominating Set Problem |
| title_sort | computational study on a ptas for planar dominating set problem |
| topic | dominating set problem PTAS branch-decomposition based algorithms planar graphs computational study |
| url | http://www.mdpi.com/1999-4893/6/1/43 |
| work_keys_str_mv | AT qianpinggu computationalstudyonaptasforplanardominatingsetproblem AT marjanmarzban computationalstudyonaptasforplanardominatingsetproblem |