{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:01:38Z","timestamp":1725494498346},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676904"},{"type":"electronic","value":"9783540449850"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_10","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T20:17:33Z","timestamp":1194985053000},"page":"97-110","source":"Crossref","is-referenced-by-count":25,"title":["Fixed Parameter Algorithms for Planar Dominating Set and Related Problems"],"prefix":"10.1007","author":[{"given":"Jochen","family":"Alber","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM 41:153\u2013180, 1994.","journal-title":"Journal of the ACM"},{"issue":"1","key":"10_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1137\/0217004","volume":"17","author":"D. Bienstock","year":"1988","unstructured":"D. Bienstock and C. L. Monma, On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 17(1):53\u201376, 1988.","journal-title":"SIAM J. Comput"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25:1305\u20131317, 1996.","journal-title":"SIAM J. Comput"},{"key":"10_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Proceedings 22nd MFCS\u201997","author":"H. L. Bodlaender","year":"1997","unstructured":"H. L. Bodlaender, Treewidth: Algorithmic techniques and results. In Proceedings 22nd MFCS\u201997, Springer-Verlag LNCS 1295, pp. 19\u201336, 1997."},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H. L. Bodlaender","year":"1998","unstructured":"H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth. Theor.Comp. Sci. 209:1\u201345, 1998.","journal-title":"Theor.Comp. Sci"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. P. Spinrad, Graph Classes: a Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"10_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1007\/3-540-63165-8_229","volume-title":"Proceedings ICALP\u201997","author":"H. J. Broersma","year":"1997","unstructured":"H. J. Broersma, T. Kloks, D. Kratsch, and H. M\u00fcller, Independent sets in AT-free graphs, In Proceedings ICALP\u201997, Springer-Verlag LNCS 1256, pp. 760\u2013770, 1997."},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M. S. Chang","year":"1998","unstructured":"M. S. Chang, Efficient algorithms for the domination problem on interval and circular arc graphs, SIAM J. Comput. 27:1671\u20131694, 1998.","journal-title":"SIAM J. Comput"},{"key":"10_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Proceedings 25th WG","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. Kanj, and W. Jia, Vertex cover: further observations and further improvements. In Proceedings 25th WG, Springer-Verlag LNCS 1665, pp. 313\u2013324, 1999."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0012-365X(90)90357-N","volume":"86","author":"D. G. Corneil","year":"1990","unstructured":"D. G. Corneil and L. K. Stewart, Dominating sets in perfect graphs, Discrete Mathematics 86, (1990), 145\u2013164.","journal-title":"Discrete Mathematics"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"P. Crescenzi and V. Kann, A compendium of NP optimization problems. Available at http:\/\/www.nada.kth.se\/theory\/problemlist.html , August 1998.","DOI":"10.1007\/3-540-63248-4_10"},{"key":"10_CR12","unstructured":"M. Damian-Iordache and S.V. Pemmaraju, A (2 + \u03b5)-approximation scheme for minimum domination on circle graphs. In Proceedings 11th ACM-SIAM SODA 2000, pp. 672\u2013679."},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows, Parameterized computational feasibility. In P. Clote, J. Remmel (eds.): Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, 1995.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"10_CR15","first-page":"69","volume":"132","author":"R. D. Dutton","year":"1998","unstructured":"R. D. Dutton and R. C. Brigham, Domination in claw-free graphs, Congr. Num. 132: 69\u201375, 1998.","journal-title":"Congr. Num."},{"key":"10_CR16","unstructured":"M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds.), Domination in graphs, Marcel Dekker, 1998.","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"10_CR18","first-page":"139","volume":"116","author":"M. A. Henning","year":"1996","unstructured":"M. A. Henning, Domination in graphs, A survey, Congr. Num. 116:139\u2013179, 1996.","journal-title":"A survey, Congr. Num."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum (ed.), Approximation algorithms for NP-hard problems. PWS Publishing Company, 1997.","DOI":"10.1145\/261342.571216"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1002\/net.3230230604","volume":"23","author":"A. Kanevsky","year":"1993","unstructured":"A. Kanevsky, Finding all minimum-size separating vertex sets in a graph, Networks 23: 533\u2013541, 1993.","journal-title":"Networks"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"J. van Leeuwen, Graph Algorithms, In Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity Theory, North Holland, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H. M\u00fcller","year":"1987","unstructured":"H. M\u00fcller and A. Brandst\u00e4dt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theor. Comp. Sci. 53:257\u2013265, 1987.","journal-title":"Theor. Comp. Sci"},{"key":"10_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Proceedings 16th STACS","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith. Upper bounds for Vertex Cover further improved. In Proceedings 16th STACS, Springer-Verlag LNCS 1563, pp. 561\u2013570, 1999."},{"key":"10_CR24","unstructured":"C. H. Papadimitriou, Computational Complexity. Addison-Wesley, 1994."},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0167-5060(08)70390-X","volume":"55","author":"R. C. Read","year":"1993","unstructured":"R. C. Read, Prospects for graph theory algorithms. Ann. Discr. Math. 55:201\u2013210, 1993.","journal-title":"Ann. Discr. Math"},{"key":"10_CR26","first-page":"157","volume":"1","author":"J. A. Telle","year":"1994","unstructured":"J. A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1:157\u2013171, 1994.","journal-title":"Nordic J. Comput"},{"issue":"4","key":"10_CR27","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J. A. Telle","year":"1997","unstructured":"J. A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SI AM J. Discr. Math. 10(4):529\u2013550, 1997.","journal-title":"SI AM J. Discr. Math"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T10:40:47Z","timestamp":1556966447000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}