{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:53Z","timestamp":1740109373000,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in polynomial time.<\/jats:p>","DOI":"10.1007\/s00224-021-10030-3","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T17:02:56Z","timestamp":1616778176000},"page":"52-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Typical Sequences Revisited \u2014 Computing Width Parameters of Graphs"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"10030_CR1","doi-asserted-by":"crossref","unstructured":"Althaus, E., Ziegler, S.: Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, CoRR, 1912.09144 (2019)","DOI":"10.1007\/978-3-030-63072-0_6"},{"issue":"4","key":"10030_CR2","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/s00453-008-9180-4","volume":"56","author":"E Amir","year":"2010","unstructured":"Amir, E.: Approximation algorithms for treewidth. Algorithmica 56(4), 448\u2013479 (2010)","journal-title":"Algorithmica"},{"issue":"6","key":"10030_CR3","doi-asserted-by":"publisher","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."},{"key":"10030_CR4","unstructured":"Bodlaender, H.L., Cai, L., Chen, J., Fellows, M.R., Telle, J.A., Marx, D.: Open problems in parameterized and exact computation \u2013 IWPEC 2006. Technical Report UU-CS-2006-052, Department of Information and Computing Sciences, Utrecht University (2006)"},{"issue":"2","key":"10030_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A ckn 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10030_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.jcss.2008.10.003","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fellows, M.R., Thilikos, D.M.: Derivation of algorithms for cutwidth and related graph layout parameters. J. Comput. Syst. Sci. 75(4), 231\u2013244 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"10030_CR7","unstructured":"Bodlaender, H.L., Gustedt, J., Telle, J.A.: Linear-time register allocation for a fixed number of registers. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp 574\u2013583. ACM\/SIAM (1998)"},{"issue":"2","key":"10030_CR8","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algor. 21(2), 358\u2013402 (1996)","journal-title":"J. Algor."},{"key":"10030_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Constructive linear time algorithms for branchwidth. In: Proceedings 24th International Colloquium on Automata, Languages and Programming, ICALP 1997, volume 1256 of Lecture Notes in Computer Science (LNCS), pp 627\u2013637. Springer (1997)","DOI":"10.1007\/3-540-63165-8_217"},{"key":"10030_CR10","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Computing small search numbers in linear time. In: Proceedings of the 1st International Workshop on Parameterized and Exact Computation, IWPEC 2004, volume 3162 of Lecture Notes in Computer Science (LNCS), pp 37\u201348. Springer (2004)","DOI":"10.1007\/978-3-540-28639-4_4"},{"key":"10030_CR11","unstructured":"Bojanczyk, M., Pilipczuk, M.: Optimizing tree decompositions in MSO. In: Vollmer, H., Vall\u00e9e, B. (eds.) Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pp 15:1\u201315:13 (2017)"},{"issue":"2","key":"10030_CR12","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629\u2013657 (2008)","journal-title":"SIAM J. Comput."},{"key":"10030_CR13","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: Faster computation of path-width. In: Proceedings 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, volume 9843 of Lecture Notes in Computer Science (LNCS), pp 385\u2013396. Springer (2016)","DOI":"10.1007\/978-3-319-44543-4_30"},{"issue":"11","key":"10030_CR14","doi-asserted-by":"publisher","first-page":"7178","DOI":"10.1109\/TIT.2017.2740283","volume":"63","author":"J Jeong","year":"2017","unstructured":"Jeong, J., Kim, E.J, Oum, S.: The \u201cart of trellis decoding\u201d is fixed-parameter tractable. IEEE Trans Inf Theory 63(11), 7178\u20137205 (2017)","journal-title":"IEEE Trans Inf Theory"},{"issue":"1","key":"10030_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0096-0551(98)00002-2","volume":"24","author":"CW Kessler","year":"1998","unstructured":"Kessler, C.W.: Scheduling expression DAGs for minimal register need. Comput. Lang. 24(1), 33\u201353 (1998)","journal-title":"Comput. Lang."},{"issue":"1","key":"10030_CR16","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.1996.0002","volume":"20","author":"J Lagergren","year":"1996","unstructured":"Lagergren, J.: Efficient parallel algorithms for graphs of bounded tree-width. J. Algor. 20(1), 20\u201344 (1996)","journal-title":"J. Algor."},{"key":"10030_CR17","doi-asserted-by":"crossref","unstructured":"Lagergren, J., Arnborg, S.: Finding minimal forbidden minors using a finite congruence. In: Proceedings of the 18th International Colloquium on Automata, Languages and Programming, ICALP 1991, volume 510 of Lecture Notes in Computer Science (LNCS), pp 532\u2013543. Springer (1991)","DOI":"10.1007\/3-540-54233-7_161"},{"key":"10030_CR18","doi-asserted-by":"crossref","unstructured":"Reed, B.A.: Finding approximate separators and computing tree width quickly. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pp 221\u2013228. ACM (1992)","DOI":"10.1145\/129712.129734"},{"issue":"1","key":"10030_CR19","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. XIII. The disjoint paths problem. J. Combinat. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Combinat. Theory Ser. B"},{"issue":"3","key":"10030_CR20","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R Sethi","year":"1975","unstructured":"Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226\u2013248 (1975)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10030_CR21","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1145\/321607.321620","volume":"17","author":"R Sethi","year":"1970","unstructured":"Sethi, R., Ullman, J.D.: The generation of optimal code for arithmetic expressions. J. ACM 17(4), 715\u2013728 (1970)","journal-title":"J. ACM"},{"key":"10030_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058520","volume-title":"Enumerative Combinatorics, 2nd edn., vol. I","author":"RP Stanley","year":"2011","unstructured":"Stanley, R.P.: Enumerative Combinatorics, 2nd edn., vol. I. Cambridge University Press, Cambridge (2011)"},{"issue":"1","key":"10030_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth i: a linear time fixed parameter algorithm. J. Algor. 56(1), 1\u201324 (2005)","journal-title":"J. Algor."},{"issue":"1","key":"10030_CR24","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: algorithms for partial w-trees of bounded degree. J. Algor. 56(1), 25\u201349 (2005)","journal-title":"J. Algor."},{"issue":"2","key":"10030_CR25","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series-parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10030-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10030-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10030-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T08:06:32Z","timestamp":1676361992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10030-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10030"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10030-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"7 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}