{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:31Z","timestamp":1761611251219,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_27","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"324-335","source":"Crossref","is-referenced-by-count":16,"title":["Computing Pathwidth Faster Than 2 n"],"prefix":"10.1007","author":[{"given":"Karol","family":"Suchan","sequence":"first","affiliation":[]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"27_CR2","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern.\u00a011, 1\u201322 (1993)","journal-title":"Acta Cybern."},{"key":"27_CR3","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 J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth, Tech. Rep. UU-CS-2006-032, Department of Information and Computing Sciences, Utrecht University (2006)","key":"27_CR4","DOI":"10.1007\/11841036_60"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11841036_60","volume-title":"Algorithms \u2013 ESA 2006","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM J. Discrete Math.\u00a08, 606\u2013616 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Math.\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U. Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput.\u00a038, 629\u2013657 (2008)","journal-title":"SIAM J. Comput."},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput.\u00a038, 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-540-70575-8_18","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Villanger, Y.: Treewidth computation and extremal combinatorics. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 210\u2013221. Springer, Heidelberg (2008)"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01462229","volume":"11","author":"M. Habib","year":"1994","unstructured":"Habib, M., Mhring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order\u00a011, 47\u201360 (1994)","journal-title":"Order"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-540-70918-3_21","volume-title":"STACS 2007","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing minimal interval completions. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 236\u2013247. Springer, Heidelberg (2007)"},{"key":"27_CR13","first-page":"201","volume-title":"Proceedings of the 1961, 16th ACM national meeting","author":"M. Held","year":"1961","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. In: Proceedings of the 1961, 16th ACM national meeting, pp. 71.201\u201371.204. ACM, New York (1961)"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C.W. Ho","year":"1989","unstructured":"Ho, C.W., Lee, R.C.T.: Counting clique trees and computing perfect elimination schemes in parallel. Information Processing Letters\u00a031, 61\u201368 (1989)","journal-title":"Information Processing Letters"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1142\/S0129054196000099","volume":"7","author":"T. Kloks","year":"1996","unstructured":"Kloks, T.: Treewidth of circle graphs. Int. J. Found. Comput. Sci.\u00a07, 111\u2013120 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Mihai, R., Todinca, I.: Pathwidth is np-hard for weighted trees. In: Faw, X., Deng, J.E. (eds.). LNCS, vol.\u00a05598, pp. 181\u2013195. Springer, Heidelberg (2009)","key":"27_CR16","DOI":"10.1007\/978-3-642-02270-8_20"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-74839-7_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K. Suchan","year":"2007","unstructured":"Suchan, K., Todinca, I.: Pathwidth of circular-arc graphs. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 258\u2013269. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T19:20:38Z","timestamp":1676575238000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}