{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T10:37:34Z","timestamp":1777804654825,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00224-011-9312-0","type":"journal-article","created":{"date-parts":[[2011,1,20]],"date-time":"2011-01-20T04:44:11Z","timestamp":1295498651000},"page":"420-432","source":"Crossref","is-referenced-by-count":44,"title":["A Note on Exact Algorithms for Vertex Ordering Problems on Graphs"],"prefix":"10.1007","volume":"50","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[]},{"given":"Arie M. C. A.","family":"Koster","sequence":"additional","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,1,21]]},"reference":[{"key":"9312_CR1","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,\u00a0H.L.: A\u00a0partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9312_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender,\u00a0H.L., Fomin,\u00a0F.V., Koster,\u00a0A.M.C.A., Kratsch,\u00a0D., Thilikos,\u00a0D.M.: On exact algorithms for treewidth. Technical Report UU-CS-2006-032, Department of Information and Computing Sciences, Utrecht University, Utrecht, the Netherlands (2006)","DOI":"10.1007\/11841036_60"},{"key":"9312_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1007\/11841036_60","volume-title":"Proceedings of the 14th Annual European Symposium on Algorithms, ESA 2006","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender,\u00a0H.L., Fomin,\u00a0F.V., Koster,\u00a0A.M.C.A., Kratsch,\u00a0D., Thilikos,\u00a0D.M.: On exact algorithms for treewidth. In: Azar,\u00a0Y., Erlebach,\u00a0T. (eds.) Proceedings of the 14th Annual European Symposium on Algorithms, ESA 2006. Lecture Notes in Computer Science, vol.\u00a04168, pp. 672\u2013683. Springer, Berlin (2006)"},{"key":"9312_CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1051\/ro:2004011","volume":"38","author":"F. Clautiaux","year":"2004","unstructured":"Clautiaux,\u00a0F., Moukrim,\u00a0A., N\u00e9gre,\u00a0S., Carlier,\u00a0J.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Oper. Res. 38, 13\u201326 (2004)","journal-title":"RAIRO Oper. Res."},{"key":"9312_CR5","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,\u00a0N.D., Kirousis,\u00a0L.M., Thilikos,\u00a0D.M.: Fugitive-search games on graphs and related parameters. Theor. Comput. Sci. 172, 233\u2013254 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9312_CR6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz,\u00a0J., Petit,\u00a0J., Serna,\u00a0M.: A survey of graph layout problems. ACM Comput. Surv. 34, 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"key":"9312_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/978-3-540-70575-8_18","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Part\u00a0I","author":"F.V. Fomin","year":"2008","unstructured":"Fomin,\u00a0F.V., Villanger,\u00a0Y.: Treewidth computation and extremal combinatorics. In: Aceto,\u00a0L., Damg\u00e5rd,\u00a0I., Goldberg,\u00a0L.A., Halld\u00f3rsson,\u00a0M.M., Ing\u00f3lfsd\u00f3ttir,\u00a0A., Walukuewics,\u00a0I. (eds.) Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Part\u00a0I. Lecture Notes in Computer Science, vol.\u00a05125, pp. 210\u2013221. Springer, Berlin (2008)"},{"key":"9312_CR8","series-title":"Dagstuhl Seminar Proceedings","first-page":"383","volume-title":"Proceedings 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","author":"F.V. Fomin","year":"2010","unstructured":"Fomin,\u00a0F.V., Villanger,\u00a0Y.: Finding induced subgraphs via minimal triangulations. In: Marion,\u00a0J.-Y., Schwentick,\u00a0T. (eds.) Proceedings 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010. Dagstuhl Seminar Proceedings, vol.\u00a05, pp.\u00a0383\u2013394. Schloss Dagstuhl, Germany (2010). Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9312_CR9","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,\u00a0F.V., Kratsch,\u00a0D., Todinca,\u00a0I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: D\u00edaz,\u00a0J., Karhum\u00e4ki,\u00a0J., Lepist\u00f6,\u00a0A., Sanella,\u00a0D. (eds.) Proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP 2004. Lecture Notes in Computer Science, vol.\u00a03142, pp. 568\u2013580. Springer, Berlin (2004)"},{"key":"9312_CR10","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin,\u00a0F.V., Kratsch,\u00a0D., Todinca,\u00a0I., Villanger,\u00a0Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38, 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"key":"9312_CR11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey,\u00a0M.R., Johnson,\u00a0D.S., Stockmeyer,\u00a0L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9312_CR12","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich,\u00a0Y., Shelah,\u00a0S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16, 486\u2013502 (1987)","journal-title":"SIAM J. Comput."},{"key":"9312_CR13","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held,\u00a0M., Karp,\u00a0R.: A\u00a0dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9312_CR14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley,\u00a0N.G.: The vertex separation number of a graph equals its path width. Inf. Process. Lett. 42, 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9312_CR15","first-page":"484","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"M. Koivisto","year":"2010","unstructured":"Koivisto,\u00a0M., Parviainen,\u00a0P.: A\u00a0space-time tradeoff for permutation problems. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 484\u2013492 (2010)"},{"key":"9312_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"Proceedings of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009","author":"K. Suchan","year":"2009","unstructured":"Suchan,\u00a0K., Villanger,\u00a0Y.: Computing pathwidth faster than\u00a02 n . In: Chen,\u00a0J., Fomin,\u00a0F.V. (eds.) Proceedings of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009. Lecture Notes in Computer Science, vol.\u00a05917, pp. 324\u2013335. Springer, Berlin (2009)"},{"key":"9312_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1007\/11682462_73","volume-title":"Proceedings of the 7th Latin American Symposium on Theoretical Informatics, LATIN 2006","author":"Y. Villanger","year":"2006","unstructured":"Villanger,\u00a0Y.: Improved exponential-time algorithms for treewidth and minimum fill-in. In: Correa,\u00a0J.R., Hevia,\u00a0A., Kiwi,\u00a0M.A. (eds.) Proceedings of the 7th Latin American Symposium on Theoretical Informatics, LATIN 2006. Lecture Notes in Computer Science, vol.\u00a03887, pp. 800\u2013811. Springer, Berlin (2006)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00224-011-9312-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T20:39:55Z","timestamp":1559939995000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9312-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,21]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9312"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9312-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,21]]}}}