{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:10:40Z","timestamp":1725516640240},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_9","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T07:18:26Z","timestamp":1219130306000},"page":"89-102","source":"Crossref","is-referenced-by-count":1,"title":["Computational Study on Dominating Set Problem of Planar Graphs"],"prefix":"10.1007","author":[{"given":"Marjan","family":"Marzban","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian-Ping","family":"Gu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Public Implementation of a Graph Algorithm Library and Editor (2008), \n                  \n                    http:\/\/pigale.sourceforge.net\/"},{"key":"9_CR2","unstructured":"The LEDA User Manual, Algorithmic Solutions, Version 4.2.1 (2008), \n                  \n                    http:\/\/www.mpi-inf.mpg.de\/LEDA\/MANUAL\/MANUAL.html"},{"key":"9_CR3","unstructured":"Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. In: Proc. of the International Network Optimization Conference (INOC 2003), pp. 1\u20136 (2003)"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmca\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmca"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-44683-4_11","volume-title":"Mathematical Foundations of Computer Science 2001","author":"J. Alber","year":"2001","unstructured":"Alber, J., Fan, H., Fellows, M., Fernau, H., Niedermeier, R.: Refined search tree technique for dominating set on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 111\u2013122. Springer, Heidelberg (2001)"},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for dominating set. Journal of the ACM\u00a051(3), 363\u2013384 (2004)","journal-title":"Journal of the ACM"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. Journal of ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of ACM"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Bian, Z., Gu, Q., Marzban, M., Tamaki, H., Yoshitake, Y.: Empirical study on branchwidth and branch decomposition of planar graphs. In: Proc. of the 9th SIAM Workshop on Algorithm Engineering and Experiments (ALENEX 2008), pp. 152\u2013165 (2008)","DOI":"10.1137\/1.9781611972887.15"},{"key":"9_CR9","unstructured":"Bian, Z., Gu, Q.-P.: Computing branch decomposition of large planar graphs. Technical report, SFU-CMPT-TR 2008-04, School of Computing Science, Simon Fraser University (2008)"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Dorn, F.: How to use planarity efficiently: new tree-decomposition based algorithms. In: Proc. of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). LNCS, vol.\u00a04769, pp. 280\u2013291 (2007)","DOI":"10.1007\/978-3-540-74839-7_27"},{"key":"9_CR13","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellow, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, Heidelberg (1999)"},{"key":"9_CR14","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. Cong. Num.\u00a087, 161\u2013187 (1992)","journal-title":"Cong. Num."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Fiege","year":"1998","unstructured":"Fiege, U.: A threshold of ln n for approximating set cover. Journal of ACM\u00a045, 634\u2013652 (1998)","journal-title":"Journal of ACM"},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM Journal on Computing\u00a036(2), 281\u2013309 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR17","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","first-page":"373","volume-title":"Automata, Languages and Programming","author":"Q.P. Gu","year":"2005","unstructured":"Gu, Q.P., Tamaki, H.: Optimal branch decomposition of planar graphs in O(n\n                        3) time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"issue":"4","key":"9_CR19","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"T.W. Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electronic power networks. SIAM J. on Discrete Mathematics\u00a015(4), 519\u2013529 (2002)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"9_CR20","volume-title":"Monographs and Textbooks in Pure and Applied Mathematics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs. In: Monographs and Textbooks in Pure and Applied Mathematics, vol.\u00a0209. Marcel Dekker, New York (1998)"},{"key":"9_CR21","volume-title":"Monographs and Textbooks in Pure and Applied Mathematics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. In: Monographs and Textbooks in Pure and Applied Mathematics, vol.\u00a0208. Marcel Dekker, New York (1998)"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/3-540-45687-2_33","volume-title":"Mathematical Foundations of Computer Science 2002","author":"I.A. Kanj","year":"2002","unstructured":"Kanj, I.A., Perkovic, L.: Improved parameterized algorithms for planar dominating set. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 399\u2013410. Springer, Heidelberg (2002)"},{"issue":"2","key":"9_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1002\/wcm.107","volume":"6","author":"X.-Y. Li","year":"2003","unstructured":"Li, X.-Y.: Algorithmic, geometric and graphs issues in wireless networks. Journal of Wireless Communications and Mobile Computing (WCMC)\u00a06(2), 119\u2013140 (2003)","journal-title":"Journal of Wireless Communications and Mobile Computing (WCMC)"},{"key":"9_CR25","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, New York (1999)"},{"key":"9_CR26","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB-A traveling salesman library. ORSA J. on Computing\u00a03, 376\u2013384 (1991)","journal-title":"ORSA J. on Computing"},{"key":"9_CR27","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors I. Excluding a forest. Journal of Combinatorial Theory Series B\u00a035, 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors X. Obstructions to tree decomposition. J. of Combinatorial Theory Series B\u00a052, 153\u2013190 (1991)","journal-title":"J. of Combinatorial Theory Series B"},{"key":"9_CR30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-001-0101-z","volume":"33","author":"L.A. Sanchis","year":"2002","unstructured":"Sanchis, L.A.: Experimental analysis of heuristic algorithms for the dominating set problem. Algorithmica\u00a033, 3\u201318 (2002)","journal-title":"Algorithmica"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Schaeffer, G.: Random sampling of large planar maps and convex polyhedra. In: Proc. of the 31st Annual ACM Symposium on the Theory of Computing (STOC 1999), pp. 760\u2013769 (1999)","DOI":"10.1145\/301250.301448"},{"issue":"2","key":"9_CR32","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"issue":"2","key":"9_CR33","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1142\/S0129054103001753","volume":"14","author":"P.J. Wan","year":"2003","unstructured":"Wan, P.J., Alzoubi, K.M., Frieder, O.: A simple heuristic for minimum connected dominating set in graphs. International Journal of Found. Comput. Sci.\u00a014(2), 323\u2013333 (2003)","journal-title":"International Journal of Found. Comput. Sci."},{"key":"9_CR34","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River (1996)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:14:24Z","timestamp":1619522064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}