{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:35Z","timestamp":1771036355897,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_77","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"931-942","source":"Crossref","is-referenced-by-count":24,"title":["A Faster Parameterized Algorithm for Treedepth"],"prefix":"10.1007","author":[{"given":"Felix","family":"Reidl","sequence":"first","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]},{"given":"Fernando S\u00e1nchez","family":"Villaamil","sequence":"additional","affiliation":[]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"77_CR1","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/S0895480195282550","volume":"11","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Deogun, J.S., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Rankings of graphs. SIAM Journal of Discrete Mathematics\u00a011(1), 168\u2013181 (1998)","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"77_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A O(ck n) 5-approximation algorithm for treewidth. CoRR, abs\/1304.6321 (2013)","DOI":"10.1109\/FOCS.2013.60"},{"issue":"2","key":"77_CR3","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms\u00a018(2), 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"key":"77_CR4","unstructured":"Bodlaender, H.L., Kratsch, D.: Personal communication (2014)"},{"key":"77_CR5","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 Theory of Graphs. I. Recognizable Sets of Finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"77_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/3-540-57785-8_187","volume-title":"STACS 94","author":"J.S. Deogun","year":"1994","unstructured":"Deogun, J.S., Kloks, T., Kratsch, D., M\u00fcller, H.: On vertex ranking for permutations and other graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 747\u2013758. Springer, Heidelberg (1994)"},{"key":"77_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2005.12.006","volume":"98","author":"D. Dereniowski","year":"2006","unstructured":"Dereniowski, D., Nadolski, A.: Vertex rankings of chordal graphs and weighted trees. Information Processing Letters\u00a098, 96\u2013100 (2006)","journal-title":"Information Processing Letters"},{"key":"77_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R. Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"key":"77_CR9","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1145\/356044.356047","volume":"9","author":"I.S. Duff","year":"1983","unstructured":"Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Transactions on Mathematical Software\u00a09, 302\u2013325 (1983)","journal-title":"ACM Transactions on Mathematical Software"},{"key":"77_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-319-03898-8_13","volume-title":"Parameterized and Exact Computation","author":"F.V. Fomin","year":"2013","unstructured":"Fomin, F.V., Giannopoulou, A.C., Pilipczuk, M.: Computing tree-depth faster than 2n. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol.\u00a08246, pp. 137\u2013149. Springer, Heidelberg (2013)"},{"issue":"1-3","key":"77_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M. Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic\u00a0130(1-3), 3\u201331 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1-3","key":"77_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(93)E0216-Q","volume":"142","author":"M. Katchalski","year":"1995","unstructured":"Katchalski, M., McCuaig, W., Seager, S.: Ordered colourings. Discrete Mathematics\u00a0142(1-3), 141\u2013154 (1995)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"77_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/110825443","volume":"34","author":"K. Kaya","year":"2013","unstructured":"Kaya, K., U\u00e7ar, B.: Constructing elimination trees for sparse unsymmetric matrices. SIAM Journal on Matrix Analysis and Applications\u00a034(2), 345\u2013354 (2013)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"77_CR14","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: FOCS, pp. 270\u2013281 (1980)","DOI":"10.1109\/SFCS.1980.13"},{"issue":"1","key":"77_CR15","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0611010","volume":"11","author":"J.W.H. Liu","year":"1990","unstructured":"Liu, J.W.H.: The role of elimination trees in sparse factorization. SIAM Journal on Matrix Analysis and Applications\u00a011(1), 134\u2013172 (1990)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"77_CR16","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal. In: Randall, D. (ed.) Proc. of 22nd SODA, pp. 777\u2013789. SIAM (2011)","DOI":"10.1137\/1.9781611973082.61"},{"issue":"3","key":"77_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics\u00a029(3), 760\u2013776 (2008)","journal-title":"European Journal of Combinatorics"},{"key":"77_CR18","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"J. Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol.\u00a028. Springer, Heidelberg (2012)"},{"key":"77_CR19","unstructured":"Pothen, A.: The complexity of optimal elimination trees. Technical Report CS-88-13, Pennsylvannia State University (1988)"},{"issue":"3","key":"77_CR20","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis and Applications\u00a011(3), 430\u2013452 (1990)","journal-title":"SIAM Journal of Matrix Analysis and Applications"},{"key":"77_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\u00a0XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"77_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"A.A. Sch\u00e4ffer","year":"1989","unstructured":"Sch\u00e4ffer, A.A.: Optimal node ranking of trees in linear time. Information Processing Letters\u00a033(2), 91\u201396 (1989)","journal-title":"Information Processing Letters"},{"key":"77_CR23","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Spectral partitioning works: Planar graphs and finite element meshes. In: FOCS, pp. 96\u2013105 (1996)","DOI":"10.1109\/SFCS.1996.548468"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_77","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:14:29Z","timestamp":1558908869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}