{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T12:41:04Z","timestamp":1792068064111,"version":"4.4.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,3]]},"DOI":"10.1007\/s00453-007-9041-6","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T18:34:03Z","timestamp":1190918043000},"page":"358-373","source":"Crossref","is-referenced-by-count":18,"title":["Nondeterministic Graph Searching: From Pathwidth to Treewidth"],"prefix":"10.1007","volume":"53","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9041_CR1","unstructured":"Amini, O., Huc, F., Perennes, S.: On the pathwidth of planar Graphs. SIAM J. Discret. Math. (to appear)"},{"key":"9041_CR2","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth, In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI-2001), San Francisco, CA, pp. 7\u201315. Morgan Kaufmann (2001)"},{"key":"9041_CR3","doi-asserted-by":"crossref","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. Algebr. Discret. Methods 8, 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"9041_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","volume":"5","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey). DIMACS Ser. Discret. Math. Theor. Comput. Sci. 5, 33\u201349 (1991)","journal-title":"DIMACS Ser. Discret. Math. Theor. Comput. Sci."},{"key":"9041_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9041_CR6","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1002\/jgt.20218","volume":"55","author":"D. Coudert","year":"2007","unstructured":"Coudert, D., Huc, F., Sereni, J.-S.: Pathwidth of outerplanar graphs. J. Graph Theory 55(1), 27\u201341 (2007)","journal-title":"J. Graph Theory"},{"key":"9041_CR7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N.D. Dendris","year":"1997","unstructured":"Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theor. Comput. Sci. 172, 233\u2013254 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9041_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"9041_CR9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.: The vertex separation and search number of a graph. Inf. Comput. 113, 50\u201379 (1994)","journal-title":"Inf. Comput."},{"key":"9041_CR10","first-page":"563","volume-title":"Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005)","author":"U. Feige","year":"2005","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 563\u2013572. ACM, New York (2005)"},{"issue":"1","key":"9041_CR11","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1002\/jgt.20219","volume":"55","author":"F.V. Fomin","year":"2007","unstructured":"Fomin, F.V., Thilikos, D.M.: On self duality of pathwidth in polyhedral graph embeddings. J. Graph Theory 55(1), 42\u201354 (2007)","journal-title":"J. Graph Theory"},{"key":"9041_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004)","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I.: Exact algorithms for treewidth and minimum fill-in. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes in Computer Science, vol. 3142, pp. 568\u2013580. Springer, Berlin (2004)"},{"key":"9041_CR13","doi-asserted-by":"crossref","unstructured":"Goldsmith, J., Levy, M., Munhenk, M.: Limited Nondeterminism. SIGACT News, Introduction to Complexity Theory, Column 13, June 1996","DOI":"10.1145\/235767.235769"},{"key":"9041_CR14","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9041_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L.M. Kirousis","year":"1986","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Searching and pebbling. Theor. Comput. Sci. 47, 205\u2013218 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9041_CR16","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"F.S. Makedon","year":"1985","unstructured":"Makedon, F.S., Papadimitriou, C.H., Sudborough, I.H.: Topological bandwidth. SIAM J. Algebr. Discret. Methods 6, 418\u2013444 (1985)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"9041_CR17","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","volume":"23","author":"F.S. Makedon","year":"1989","unstructured":"Makedon, F.S., Sudborough, I.H.: On minimizing width in linear layouts. Discret. Appl. Math. 23, 243\u2013265 (1989)","journal-title":"Discret. Appl. Math."},{"key":"9041_CR18","doi-asserted-by":"crossref","unstructured":"Mazoit, F., Nisse, N.: Monotonicity property of non-deterministic graph searching. In: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) (to appear)","DOI":"10.1007\/978-3-540-74839-7_4"},{"key":"9041_CR19","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Ser. B 52, 153\u2013190 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9041_CR20","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P. Seymour","year":"1993","unstructured":"Seymour, P., Thomas, R.: Graph searching and a min-max theorem for tree-width. J. Comb. Theory Ser. B 58, 22\u201333 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9041_CR21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P. Seymour","year":"1994","unstructured":"Seymour, P., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"9041_CR22","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6, 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"key":"9041_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization: \u201cEureka, you shrink\u201d","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization: \u201cEureka, you shrink\u201d. Lecture Notes in Computer Science, vol. 2570, pp. 185\u2013207. Springer, Berlin (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9041-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9041-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9041-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:44:59Z","timestamp":1559137499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9041-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["9041"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9041-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}