{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T20:20:44Z","timestamp":1790972444519,"version":"4.1.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in O((log n)\n                    <jats:sup>2<\/jats:sup>\n                    ) time using O(n) operations on the EREW PRAM. We also give faster parallel algorithms with optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On n-vertex input graphs, the algorithms use O(n) operations together with O(log n log\n                    <jats:sup>*<\/jats:sup>\n                    n) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.\n                  <\/jats:p>","DOI":"10.1137\/s0097539795289859","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1725-1746","source":"Crossref","is-referenced-by-count":70,"title":["Parallel Algorithms with Optimal Speedup for Bounded Treewidth"],"prefix":"10.1137","volume":"27","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torben","family":"Hagerup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90017-5"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759076"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169807"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender,\n                      NC\u2010algorithms for graphs with small treewidth\n                      , in Proc. 14th International Workshop on Graph\u2010Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 344, J. van Leeuwen, ed., Springer\u2010Verlag, Berlin, 1989, pp. 1\u201310.","DOI":"10.1007\/3-540-50728-0_32"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Hans Bodlaender, On reduction algorithms for graphs with small treewidth, Lecture Notes in Comput. Sci., Vol. 790, Springer, Berlin, 1994, 45\u20135695b:05186","DOI":"10.1007\/3-540-57899-4_40"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90018-3"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Hans Bodlaender, Babette de Fluiter, Parallel algorithms for series parallel graphs, Lecture Notes in Comput. Sci., Vol. 1136, Springer, Berlin, 1996, 277\u20132891469237","DOI":"10.1007\/3-540-61680-2_62"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"R15","unstructured":"N. Chandrasekharan,\n                      Fast Parallel Algorithms and Enumeration Techniques for Partial k\u2010Trees\n                      , Ph.D. thesis, Clemson University, Clemson, SC, 1989."},{"key":"R16","unstructured":"N. Chandrasekharan and S. T. Hedetniemi,\n                      Fast parallel algorithms for tree decomposing and parsing partial k\u2010trees\n                      , in Proc. 26th Annual Allerton Conference on Communication, Control, and Computing, Urbana\u2010Champaign, IL, 1988, pp. 283\u2013292."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0217009"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762121"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90036-9"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90042-1"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80079-0"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Babette de Fluiter, Hans Bodlaender, Parallel algorithms for treewidth two, Lecture Notes in Comput. Sci., Vol. 1335, Springer, Berlin, 1997, 157\u20131701639674","DOI":"10.1007\/BFb0024496"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"H. Gazit, G. L. Miller, and S.\u2010H. Teng,\n                      Optimal tree contraction in an EREW model\n                      , in Concurrent Computations: Algorithms, Architecture, and Technology, S. K. Tewksbury, B. W. Dickinson, and S. C. Schwartz, eds., Plenum Press, New York, 1988, pp. 139\u2013156.","DOI":"10.1007\/978-1-4684-5511-3_9"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90027-8"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0404031"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90034-F"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1023"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0218020"},{"key":"R31","unstructured":"Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde, Characterizations of k\u2010terminal flow networks and computing network flows in partial k\u2010trees, ACM, New York, 1995, 641\u20136491321885"},{"key":"R32","volume-title":"An introduction to the theory of numbers","author":"Niven Ivan","year":"1991"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0220022"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"S. Kosaraju, Arthur Delcher, Optimal parallel evaluation of tree\u2010structured computations by raking (extended abstract), Lecture Notes in Comput. Sci., Vol. 319, Springer, New York, 1988, 101\u20131101017464","DOI":"10.1007\/BFb0040378"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0002"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Jens Lagergren, Stefan Arnborg, Finding minimal forbidden minors using a finite congruence, Lecture Notes in Comput. Sci., Vol. 510, Springer, Berlin, 1991, 532\u20135431129933","DOI":"10.1007\/3-540-54233-7_161"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172769"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90020-Y"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif,\n                      Parallel tree contraction and its application\n                      , in Proc. 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1019"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"B. A. Reed,\n                      Finding approximate separators and computing tree width quickly\n                      , in Proc. 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 221\u2013228.","DOI":"10.1145\/129712.129734"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1022"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795289859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:19Z","timestamp":1787336059000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795289859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795289859"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795289859","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}