{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T15:15:55Z","timestamp":1720019755588},"reference-count":36,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2003,12,1]],"date-time":"2003-12-01T00:00:00Z","timestamp":1070236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3516,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,12]]},"DOI":"10.1016\/s0022-0000(03)00072-2","type":"journal-article","created":{"date-parts":[[2003,11,20]],"date-time":"2003-11-20T13:03:07Z","timestamp":1069333387000},"page":"808-832","source":"Crossref","is-referenced-by-count":18,"title":["Graph separators: a parameterized view"],"prefix":"10.1016","volume":"67","author":[{"given":"Jochen","family":"Alber","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00072-2_BIB1","doi-asserted-by":"crossref","unstructured":"J. Alber, H.L. Bodlaender, H. Fernau, R. Niedermeier, Fixed parameter algorithms for planar dominating set and related problems, in: Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory SWAT\u201900, Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000, pp. 97\u2013110, long version to appear in Algorithmica.","DOI":"10.1007\/3-540-44985-X_10"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB2","unstructured":"J. Alber, H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, U. Stege, Refined search tree techniques for the planar dominating set problem, in: Proceedings of the 26th International Symposium Mathematical Foundations of Computer Science MFCS\u201901, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, 2001, pp. 111\u2013122."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB3","doi-asserted-by":"crossref","unstructured":"J. Alber, M.R. Fellows, R. Niedermeier, Efficient data reduction for dominating set: a linear problem kernel for the planar case, Manuscript, April 2002.","DOI":"10.1007\/3-540-45471-3_16"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB4","doi-asserted-by":"crossref","unstructured":"J. Alber, H. Fernau, R. Niedermeier, Graph separators: a parameterized view, Technical Report WSI-2001-8, Universit\u00e4t T\u00fcbingen (Germany), Wilhelm-Schickard-Institut f\u00fcr Informatik, September 2001.","DOI":"10.1007\/3-540-44679-6_35"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB5","unstructured":"J. Alber, H. Fernau, R. Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Technical Report TR01-023, ECCC Reports, Trier, March 2001, Extended abstract in Proceedings of the 28th International Colloquium on Automata, Languages and Programming ICALP\u201901, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 261\u2013272."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","article-title":"Faster exact algorithms for hard problems","volume":"229","author":"Alber","year":"2001","journal-title":"Discrete Math."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/S0895480194272183","article-title":"Linear algorithms for partitioning embedded graphs of bounded genus","volume":"9","author":"Aleksandrov","year":"1996","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB8","doi-asserted-by":"crossref","unstructured":"N. Alon, P.D. Seymour, R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in: Proceedings of the 22nd ACM Symposium on the Theory of Computing STOC\u201990, Baltimore, MD, May 14\u201316, 1990, pp. 293\u2013299.","DOI":"10.1145\/100216.100254"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB9","first-page":"801","article-title":"A separator theorem for nonplanar graphs","volume":"3","author":"Alon","year":"1990","journal-title":"J. AMS"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB10","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","article-title":"A partial k-arboretum of graphs with bounded treewidth","volume":"209","author":"Bodlaender","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB12","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","article-title":"Vertex cover","volume":"41","author":"Chen","year":"2001","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB13","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1006\/jagm.2001.1178","article-title":"Approximation algorithms for independent sets in map graphs","volume":"41","author":"Chen","year":"2001","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB14","first-page":"127","volume":"49","author":"Chen","year":"2002","journal-title":"Map graphs, J. ACM"},{"issue":"2","key":"10.1016\/S0022-0000(03)00072-2_BIB15","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1137\/0603022","article-title":"On the problem of partitioning planar graphs","volume":"3","author":"Djidjev","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB16","first-page":"319","article-title":"A separator theorem for graphs of fixed genus","volume":"11","author":"Djidjev","year":"1985","journal-title":"Serdica"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s002360050082","article-title":"Reduced constants for simple cycle graph separation","volume":"34","author":"Djidjev","year":"1997","journal-title":"Acta Inform."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB18","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB19","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s004530010020","article-title":"Diameter and treewidth in minor-closed graph families","volume":"27","author":"Eppstein","year":"2000","journal-title":"Algorithmica"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB20","doi-asserted-by":"crossref","unstructured":"M.R. Fellows, Parameterized complexity: the main ideas and some research frontiers, in: Proceedings of the 12th Annual International Symposium on Algorithms And Computation ISAAC\u201901, Lecture Notes in Computer Science, Vol. 2223, 2001, pp. 291\u2013307.","DOI":"10.1007\/3-540-45678-3_26"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB21","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB22","unstructured":"M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2001, to appear."},{"issue":"2","key":"10.1016\/S0022-0000(03)00072-2_BIB23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"10.1016\/S0022-0000(03)00072-2_BIB24","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB25","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","article-title":"Vertex packing","volume":"8","author":"Nemhauser","year":"1975","journal-title":"Math. Programming"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB26","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, P. Rossmanith, Upper bounds for Vertex Cover further improved, in: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science STACS\u201999, Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 561\u2013570.","DOI":"10.1007\/3-540-49116-3_53"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB27","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, P. Rossmanith, On efficient fixed parameter algorithms for weighted vertex cover, in: Proceedings of the 11th Annual International Symposium on Algorithms And Computation ISAAC\u201900, Lecture Notes in Computer Science, Vol. 1969, Springer, Berlin, 2000, pp. 180\u2013191.","DOI":"10.1007\/3-540-40996-3_16"},{"issue":"2","key":"10.1016\/S0022-0000(03)00072-2_BIB28","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/254180.254190","article-title":"A survey of approximately optimal solutions to some covering and packing problems","volume":"29","author":"Paschos","year":"1997","journal-title":"ACM Comput. Surveys"},{"issue":"6","key":"10.1016\/S0022-0000(03)00072-2_BIB29","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(87)90206-7","article-title":"An application of the planar separator theorem to counting problems","volume":"25","author":"Ravi","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB30","doi-asserted-by":"crossref","unstructured":"N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the 28th ACM Symposium on the Theory of Computing STOC\u201996, 1996, pp. 571\u2013575.","DOI":"10.1145\/237814.238005"},{"issue":"3","key":"10.1016\/S0022-0000(03)00072-2_BIB31","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","article-title":"Algorithms for maximum independent sets","volume":"7","author":"Robson","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB32","doi-asserted-by":"crossref","unstructured":"D.A. Spielman, S.-H. Teng, Disk packings and planar separators, in: SCG 96: 12th Annual ACM Symposium on Computational Geometry, 1996, pp. 349\u2013358.","DOI":"10.1145\/237218.237404"},{"key":"10.1016\/S0022-0000(03)00072-2_BIB33","first-page":"157","article-title":"Complexity of domination-type problems in graphs","volume":"1","author":"Telle","year":"1994","journal-title":"Nordic J. Comput."},{"key":"10.1016\/S0022-0000(03)00072-2_BIB34","doi-asserted-by":"crossref","unstructured":"J.A. Telle, A. Proskurowski, Practical algorithms on partial k-trees with an application to domination-like problems, in: Proceedings of the 3rd Algorithms and Data Structures WADS\u201993, Lecture Notes in Computer Science, Vol. 709, Springer, Berlin, 1993, pp. 610\u2013621.","DOI":"10.1007\/3-540-57155-8_284"},{"issue":"4","key":"10.1016\/S0022-0000(03)00072-2_BIB35","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","article-title":"Algorithms for vertex partitioning problems on partial k-trees","volume":"10","author":"Telle","year":"1997","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10.1016\/S0022-0000(03)00072-2_BIB36","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","article-title":"Edge dominating sets in graphs","volume":"38","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl. Math."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000722?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000722?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,27]],"date-time":"2020-03-27T04:41:13Z","timestamp":1585284073000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12]]}},"alternative-id":["S0022000003000722"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00072-2","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}