{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T13:32:04Z","timestamp":1772717524863,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,10]],"date-time":"2015-06-10T00:00:00Z","timestamp":1433894400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0015-9","type":"journal-article","created":{"date-parts":[[2015,6,11]],"date-time":"2015-06-11T00:56:26Z","timestamp":1433984186000},"page":"138-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing Directed Pathwidth in $$O(1.89^{n})$$ O ( 1 . 89 n ) Time"],"prefix":"10.1007","volume":"75","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","published-online":{"date-parts":[[2015,6,10]]},"reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"crossref","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. Gr. Comb. 22(2), 161\u2013172 (2006)","journal-title":"Gr. Comb."},{"issue":"1\u20132","key":"15_CR2","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201323 (1993)","journal-title":"Acta Cybern."},{"issue":"6","key":"15_CR3","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"15_CR4","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.: A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50(3), 420\u2013432 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"15_CR5","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM J. Discrete Math. 8(4), 606\u2013616 (1995)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"15_CR6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"HL Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 6(2), 181\u2013188 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Coudert, D., Mazauric, D., Nisse, N.: Experimental evaluation of a branch and bound algorithm for computing pathwidth. In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA2014), Lecture Notes in Computer Science, vol. 8504, pp. 46\u201358 (2014)","DOI":"10.1007\/978-3-319-07959-2_5"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Giannopoulou, A.C., Pilipczuk, P.: Computing tree-depth faster than $$2^n$$ 2 n . In: Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC2013), Lecture Notes in Computer Sciencs, vol. 8246, pp. 137\u2013149 (2013)","DOI":"10.1007\/978-3-319-03898-8_13"},{"key":"15_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"15_CR10","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Sciencs (STACS2010), Leibniz International Proceedings in Informatics, vol. 5, pp. 383\u2013394 (2010)"},{"issue":"3","key":"15_CR11","doi-asserted-by":"crossref","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 Appl. Math. 45(3), 233\u2013248 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"15_CR12","doi-asserted-by":"crossref","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 11(1), 44\u201360 (1994)","journal-title":"Order"},{"issue":"1","key":"15_CR13","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 82(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"15_CR14","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":"15_CR15","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"GN Kinnersley","year":"1992","unstructured":"Kinnersley, G.N.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in $$O(1.89^n)$$ O ( 1 . 89 n ) time. In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC2012), Lecture Notes in Computer Science, vol. 7535, pp. 182\u2013193 (2012)","DOI":"10.1007\/978-3-642-33293-7_18"},{"key":"15_CR17","unstructured":"Kobayashi, Y., Komuro, K. Tamaki, H.: Search space reduction through commitments in pathwidth computation: An experimental study. In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA2014), Lecture Notes in Computer Science, vol. 8504, pp. 388\u2013399 (2014)"},{"key":"15_CR18","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 (ESA1993), Lecture Notes in Computer Science, vol. 726, pp. 260\u2013271 (1993)","DOI":"10.1007\/3-540-57273-2_61"},{"issue":"1\u20133","key":"15_CR19","doi-asserted-by":"crossref","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 cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58(1\u20133), 209\u2013229 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Nagamochi, H.: Linear layouts in submodular systems. In: Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC2012), Lecture Notes in Computer Science, vol. 7676 pp. 475\u2013484 (2012)","DOI":"10.1007\/978-3-642-35261-4_50"},{"issue":"1","key":"15_CR21","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"15_CR22","doi-asserted-by":"crossref","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 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Suchan, K., Todinca, I.: Pathwidth of circular-arc graphs. In: Proceedings of 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG2007), Lecture Notes in Computer Science, vol. 4769, pp. 258\u2013269 (2007)","DOI":"10.1007\/978-3-540-74839-7_25"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Suchan, K., Villanger, Y.: Computing pathwidth faster than $$2^n$$ 2 n . In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC2009), Lecture Notes in Computer Science, vol. 5917, pp. 324\u2013335 (2009)","DOI":"10.1007\/978-3-642-11269-0_27"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Tamaki, H.: A polynomial time algorithm for bounded directed pathwidth. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2011), Lecture Notes in Computer Science, vol. 6986, pp. 331\u2013342 (2011)","DOI":"10.1007\/978-3-642-25870-1_30"},{"issue":"10","key":"15_CR26","doi-asserted-by":"crossref","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 Appl. Math. 156(10), 1822\u20131837 (2008)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0015-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0015-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0015-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T11:56:14Z","timestamp":1566820574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0015-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,10]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0015-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,10]]}}}