{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:31Z","timestamp":1761611311531},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_18","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T06:50:58Z","timestamp":1346223058000},"page":"182-193","source":"Crossref","is-referenced-by-count":11,"title":["Computing Directed Pathwidth in O(1.89 n ) Time"],"prefix":"10.1007","author":[{"given":"Kenta","family":"Kitsunai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keita","family":"Komuro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisao","family":"Tamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshihiro","family":"Tano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"18_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J. Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics\u00a022(2), 161\u2013172 (2006)","journal-title":"Graphs and Combinatorics"},{"key":"18_CR2","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A Tourist Guide Through Treewidth. Acta Cybernetica\u00a011, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"18_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 Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"18_CR4","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"H.L. Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Kratsch, D., Thilikos, D.: A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. Theory of Computing Systems\u00a050(3), 420\u2013432 (2012)","journal-title":"Theory of Computing Systems"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-56939-1_66","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and Pathwidth of Permutation Graphs. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 114\u2013125. Springer, Heidelberg (1993)"},{"issue":"2","key":"18_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The Pathwidth and Treewidth of Cographs. SIAM Journal on Discrete Mathematics\u00a06(2), 181\u2013188 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gusted","year":"1993","unstructured":"Gusted, J.: On the pathwidth of chordal graphs. Discrete Applied Mathematics\u00a045(3), 233\u2013248 (1993)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/BF01462229","volume":"11","author":"M. Habib","year":"1994","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order\u00a011(1), 44\u201360 (1994)","journal-title":"Order"},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. Journal of Combinatorial Theory, Series B\u00a082(1), 138\u2013154 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR11","unstructured":"Kashiwabara, T., Fujisawa, T.: NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph. In: Proceedings of International Symposium on Circuits and Systems, pp. 657\u2013660 (1979)"},{"issue":"6","key":"18_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"G.N. Kinnersley","year":"1992","unstructured":"Kinnersley, G.N.: The vertex separation number of a graph equals its path-width. Information Processing Letters\u00a042(6), 345\u2013350 (1992)","journal-title":"Information Processing Letters"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Kloks, T., Bodlaender, H.L., M\u00fcller, H., Kratsch, D.: Computing treewidth and minimum fill-in: All you need are the minimal separators. In: Proceedings of the 1st Annual European Symposium on Algorithms, pp. 260\u2013271 (1993)","DOI":"10.1007\/3-540-57273-2_61"},{"issue":"1-3","key":"18_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min cur is NP-complete for edge weighted trees. Theoretical Computer Science\u00a058(1-3), 209\u2013229 (1988)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B\u00a035(1), 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR16","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 VIII The disjoint paths peoblem. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR17","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)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"Parameterized and Exact Computation","author":"K. Suchan","year":"2009","unstructured":"Suchan, K., Villanger, Y.: Computing Pathwidth Faster Than 2\n                  n\n                . In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 324\u2013335. Springer, Heidelberg (2009)"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-25870-1_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Tamaki","year":"2011","unstructured":"Tamaki, H.: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 331\u2013342. Springer, Heidelberg (2011)"},{"issue":"10","key":"18_CR20","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.dam.2007.08.045","volume":"156","author":"B. Yang","year":"2008","unstructured":"Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discrete Applied Mathematics\u00a0156(10), 1822\u20131837 (2008)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:03:24Z","timestamp":1620115404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}