{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:12:57Z","timestamp":1760220777302,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T00:00:00Z","timestamp":1358726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a6010043","type":"journal-article","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T10:58:53Z","timestamp":1358765933000},"page":"43-59","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computational Study on a PTAS for Planar Dominating Set Problem"],"prefix":"10.3390","volume":"6","author":[{"given":"Marjan","family":"Marzban","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby BC, V5A 1S6, Canada"}]},{"given":"Qian-Ping","family":"Gu","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby BC, V5A 1S6, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2013,1,21]]},"reference":[{"key":"ref_1","unstructured":"Berge, C. (1973). Graphs and Hypergraphs, American Elsevier."},{"key":"ref_2","unstructured":"Liu, C. (1963). Introduction to Combinatorial Mathematics, McGraw-Hill."},{"key":"ref_3","unstructured":"Norman, R., Harary, F., and Cartwright, D. (1966). Structural Models: An Introduction to the Theory of Directed Graphs, Wiley."},{"key":"ref_4","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker."},{"key":"ref_5","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker."},{"key":"ref_6","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, a Guide to the Theory of NP-Completeness, Freeman."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. Syst. Sci"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Fiege","year":"1998","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","article-title":"Approximation algorithms for NP-complete problems on planar graphs","volume":"41","author":"Baker","year":"1994","journal-title":"J. ACM"},{"key":"ref_10","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Monographs in Computer Science, Springer-Verlag."},{"key":"ref_11","first-page":"47","article-title":"Some new techniques in design and analysis of exact (exponential) algorithms","volume":"87","author":"Fomin","year":"2005","journal-title":"Bull. EATCS"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/990308.990309","article-title":"Polynomial time data reduction for dominating set","volume":"51","author":"Alber","year":"2004","journal-title":"J. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","article-title":"Fixed parameter algorithms for dominating set and related problems on planar graphs","volume":"33","author":"Alber","year":"2002","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/S0097539702419649","article-title":"Dominating sets in planar graphs: Branch-width and exponential speed-up","volume":"36","author":"Fomin","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_15","unstructured":"Kanj, I.A., and Perkovic, L. (, January Augaust,). Improved Parameterized Algorithms for Planar Dominating Set. Proceedings of the 27th Mathematical Foundations of Computer Science. LNCS 2420, Warsaw, Poland."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","article-title":"Graph minors X. Obstructions to tree decomposition","volume":"52","author":"Robertson","year":"1991","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"30:1","DOI":"10.1145\/1367064.1367070","article-title":"Optimal branch-decomposition of planar graphs in O(n3) time","volume":"4","author":"Gu","year":"2008","journal-title":"ACM Trans. Algorithm"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","article-title":"Call routing and the ratcatcher","volume":"14","author":"Seymour","year":"1994","journal-title":"Combinatorica"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1002\/jgt.20121","article-title":"New upper bounds on the decomposability of planar graphs","volume":"51","author":"Fomin","year":"2006","journal-title":"J. Graph Theory"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Dorn, F. (, January September,). Dynamic Programming and Fast Matrix Multiplication. Proceedings of the 14th Annual European Symposium on Algorithms (ESA2006) LNCS 4168, Zurich, Switerland.","DOI":"10.1007\/11841036_27"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5455","DOI":"10.1016\/j.tcs.2009.04.012","article-title":"Computational study on planar dominating set problem","volume":"410","author":"Marzban","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-001-0101-z","article-title":"Experimental analysis of heuristic algorithms for the dominating set problem","volume":"33","author":"Sanchis","year":"2002","journal-title":"Algorithmica"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","article-title":"Efficient planarity testing","volume":"21","author":"Hopcroft","year":"1974","journal-title":"J. ACM"},{"key":"ref_24","unstructured":"Tamaki, H. (2003, January 16\u201319). A linear Time Heuristic for the Branch-decomposition of Planar Graphs. Proceedings of the 11th Annual European Symposium, Budapest, Hungary."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB-A traveling salesman library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"ref_26","unstructured":"Library of Efficient Data Types and Algorithms, Version 5.2. Available online: http:\/\/www.algorithmic-solutions.com\/leda\/index.html."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/43\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:44:26Z","timestamp":1760219066000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,21]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2013,3]]}},"alternative-id":["a6010043"],"URL":"https:\/\/doi.org\/10.3390\/a6010043","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,1,21]]}}}