{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:30:08Z","timestamp":1725507008369},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_18","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T04:38:35Z","timestamp":1207197515000},"page":"206-215","source":"Crossref","is-referenced-by-count":3,"title":["Optimization and Recognition for K 5-minor Free Graphs in Linear Time"],"prefix":"10.1007","author":[{"given":"Bruce","family":"Reed","sequence":"first","affiliation":[]},{"given":"Zhentao","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"18_CR1","doi-asserted-by":"publisher","first-page":"801","DOI":"10.2307\/1990903","volume":"3","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. Journal of the American Mathematical Society\u00a03(4), 801\u2013808 (1990)","journal-title":"Journal of the American Mathematical Society"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for np-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023, 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR3","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach.\u00a041, 153\u2013180 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"15th International Colloquium on Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming algorithms on graphs of bounded tree-width. In: Lepisto, T., Salomaa, A. (eds.) 15th International Colloquium on Automata, Languages and Programming, vol.\u00a0317, pp. 105\u2013118. Springer, Heidelberg (1988)"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms\u00a011, 631\u2013643 (1990)","journal-title":"Journal of Algorithms"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second order logic of graphs. I. recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"issue":"2","key":"18_CR8","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E. Demaine","year":"2004","unstructured":"Demaine, E., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. Journal of Computer and System Sciences\u00a069(2), 166\u2013195 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"18_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"E. Demaine","year":"2005","unstructured":"Demaine, E., Hajiaghayi, M., Thilikos, D.: Exponential speedup of fixed parameter algorithms on k. Algorithmica\u00a041(4), 245\u2013267 (2005)","journal-title":"Algorithmica"},{"key":"18_CR10","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation and coloring. In: Proc. 46th Ann. IEEE Symp. Found. Comp. Sci., pp. 637\u2013646 (2005)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G. Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica\u00a015, 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"18_CR12","first-page":"77","volume-title":"Graph Drawing, Colonial Williamsburg, 2000","author":"C. Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of spqr-trees. In: Marks, J. (ed.) Graph Drawing, Colonial Williamsburg, 2000, pp. 77\u201390. Springer, Heidelberg (2001)"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"3","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput.\u00a03, 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"18_CR14","unstructured":"Kawarabayashi, K., Li, Z., Reed, B.: Near linear time algorithms for optimization and recognition for minor closed families (in preparation)"},{"key":"18_CR15","first-page":"345","volume-title":"Third Annual Symposium on Discrete Algorithms","author":"A. K\u00e9zdy","year":"1992","unstructured":"K\u00e9zdy, A., McGuinness, P.: Sequential and parallel algorithms to find a k5 minor. In: Third Annual Symposium on Discrete Algorithms, pp. 345\u2013356. Springer, Heidelberg (1992)"},{"key":"18_CR16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"16","author":"C. Kuratowski","year":"1930","unstructured":"Kuratowski, C.: Sur le probl\u00e8me des courbes gauches en topologie. Fundamenta Mathematica\u00a016, 271\u2013283 (1930)","journal-title":"Fundamenta Mathematica"},{"issue":"2","key":"18_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Reed, B., Robertson, N., Schrijver, L., Seymour, P.: Finding disjoint trees in planar graphs in linear time. In: Graph Structure Theory, pp. 295\u2013302. AMS (1993)","DOI":"10.1090\/conm\/147\/01180"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Reed, B., Wood, D.: Fast separation in a graph with an excluded minor. In: EuroConference on Combinatorics, Graph Theory and Applications, pp. 45\u201350 (2005)","DOI":"10.46298\/dmtcs.3419"},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII: the disjoint paths problem. J. Comb. Theory Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. excluding a non-planar graph. Journal of Combinatorial Theory, Series B\u00a089, 43\u201376 (2003)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"18_CR23","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. wagner\u2019s conjecture. J. Comb. Theory Ser. B\u00a092(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"J. Lagergren","year":"1991","unstructured":"Lagergren, J., Arnborg, S., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput.\u00a01, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine eigenschaft der ebenen komplexe. Math. Ann.\u00a0114, 570\u2013590 (1937)","journal-title":"Math. Ann."}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,6]],"date-time":"2021-09-06T22:50:15Z","timestamp":1630968615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_18","relation":{},"subject":[]}}