{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:56Z","timestamp":1761611216411},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_22","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"261-272","source":"Crossref","is-referenced-by-count":25,"title":["Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems"],"prefix":"10.1007","author":[{"given":"Jochen","family":"Alber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"22_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Proc. 7th SWAT","author":"J. Alber","year":"2000","unstructured":"J. Alber, H. Bodlaender, H. Fernau, and R. Niedermeier. Fixed parameter algorithms for planar dominating set and related problems. In Proc. 7th SWAT, vol. 1851 of LNCS, Springer, pp. 97\u2013110, 2000. Full version available as Technical Report UU-CS-2000-28, Utrecht University, 2000."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"J. Alber, H. Fernau, and R. Niedermeier. Parameterized complexity: exponential speed-up for planar graph problems. Technical Report TR01-023, ECCC Reports, Trier, March 2001. Available through http:\/\/www.eccc.uni-trier.de\/eccc\/ .","DOI":"10.1007\/3-540-48224-5_22"},{"key":"22_CR3","unstructured":"J. Alber, H. Fernau, and R. Niedermeier. Graph separators: a parameterized view. To appear in Proc. 7th COCOON, 2001. Full version available as Technical Report WSI-2001-8, Universit\u00e4t T\u00fcbingen (Germany), Wilhelm-Schickard-Institut F\u00fcr Informatik, March 2001."},{"issue":"1","key":"22_CR4","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. J. ACM, 41(1):153\u2013180, 1994.","journal-title":"J. ACM"},{"key":"22_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Proc. 22nd MFCS","author":"H. L. Bodlaender","year":"1997","unstructured":"H. L. Bodlaender. Treewidth: Algorithmic techniques and results. In Proc. 22nd MFCS, vol. 1295 of LNCS, Springer, pp. 19\u201336, 1997."},{"key":"22_CR6","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":"22_CR7","doi-asserted-by":"crossref","unstructured":"L. Cai and D. Juedes. Subexponential parameterized algorithms collapse the Whierarchy. In Proc. 28th ICALP, 2001.","DOI":"10.1007\/3-540-48224-5_23"},{"key":"22_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Proc. 25th WG","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. In Proc. 25th WG, vol. 1665 of LNCS, Springer, pp. 313\u2013324, 1999."},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H. N. Djidjev","year":"1997","unstructured":"H. N. Djidjev and S. Venkatesan. Reduced constants for simple cycle graph separation. Acta Informatica, 34:231\u2013243, 1997.","journal-title":"Acta Informatica"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"22_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"T. Kloks. Treewidth: Computations and Approximations, vol. 842 of LNCS, Springer, 1994."},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comp., 9(3):615\u2013627, 1980.","journal-title":"SIAM J. Comp."},{"key":"22_CR13","volume-title":"LEDA: A Platform of Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"K. Mehlhorn and S. N\u00e4her. LEDA: A Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, England, 1999."},{"key":"22_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Proc. 16th STACS","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith. Upper Bounds for Vertex Cover further improved. In Proc. 16th STACS, vol. 1563 of LNCS, Springer, pp. 561\u2013570, 1999."},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and J. L. E. Trotter. Vertex packing: structural properties and algorithms. Math. Progr., 8:232\u2013248, 1975.","journal-title":"Math. Progr."},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas. Efficiently four-coloring planar graphs. In Proc. 28th STOC, ACM Press, pp. 571\u2013575, 1996.","DOI":"10.1145\/237814.238005"},{"key":"22_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/3-540-57155-8_284","volume-title":"Proc. 3rd WADS","author":"J. A. Telle","year":"1993","unstructured":"J. A. Telle and A. Proskurowski. Practical algorithms on partial k-trees with an application to domination-like problems. In Proc. 3rd WADS, vol. 709 of LNCS, Springer, pp. 610\u2013621, 1993."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:28:09Z","timestamp":1556936889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}