Typical Sequences Revisited — Computing Width Parameters of Graphs

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 bottlene...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2023-02, Vol.67 (1), p.52-88
Main Authors: Bodlaender, Hans L., Jaffke, Lars, Telle, Jan Arne
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Dynamic programming
Graph theory
Graphs
Polynomials
Run time (computers)
Sequences
Special Issue on Theoretical Aspects of Computer Science (STACS 2020)
Theorems
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743
cites cdi_FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743
container_end_page 88
container_issue 1
container_start_page 52
container_title Theory of computing systems
container_volume 67
creator Bodlaender, Hans L.
Jaffke, Lars
Telle, Jan Arne
description 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.
doi_str_mv 10.1007/s00224-021-10030-3
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2776278406</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2776278406</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743</originalsourceid><addsrcrecordid>eNp9kEFOwzAQRS0EEqVwAVaWWBsmtpPYS1SgIFUCQRFLy0nGbao2CXaK1B2H4IScBEOQ2LGaGen9P1-fkNMEzhOA_CIAcC4Z8ITFWwATe2SUSCEYSA37PztnUqRwSI5CWEGEFMCIXM13XV3aNX3C1y02JQb6iG91qHus6Of7B520m27b182CvtRVv6QP1tsN9ugDbR2detstwzE5cHYd8OR3jsnzzfV8cstm99O7yeWMlSITPUNXYCUgcwmiqlyRps7JSuZFoRXoIq2wslpxJaUuLJZKl2mMKaTmQmvIpRiTs8G3821MG3qzare-iS8Nz_OM50pCFik-UKVvQ_DoTOfrjfU7k4D5bssMbZnYlvlpy4goEoMoRLhZoP-z_kf1BcKEbSo</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2776278406</pqid></control><display><type>article</type><title>Typical Sequences Revisited — Computing Width Parameters of Graphs</title><source>Springer Nature</source><source>ABI/INFORM Global (ProquesT)</source><source>BSC - Ebsco (Business Source Ultimate)</source><creator>Bodlaender, Hans L. ; Jaffke, Lars ; Telle, Jan Arne</creator><creatorcontrib>Bodlaender, Hans L. ; Jaffke, Lars ; Telle, Jan Arne</creatorcontrib><description>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.</description><identifier>ISSN: 1432-4350</identifier><identifier>EISSN: 1433-0490</identifier><identifier>DOI: 10.1007/s00224-021-10030-3</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Computer Science ; Dynamic programming ; Graph theory ; Graphs ; Polynomials ; Run time (computers) ; Sequences ; Special Issue on Theoretical Aspects of Computer Science (STACS 2020) ; Theorems ; Theory of Computation</subject><ispartof>Theory of computing systems, 2023-02, Vol.67 (1), p.52-88</ispartof><rights>The Author(s) 2021</rights><rights>The Author(s) 2021. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743</citedby><cites>FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743</cites><orcidid>0000-0002-9297-3330 ; 0000-0003-4856-5863</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2776278406/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2776278406?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,11667,27901,27902,36037,44339,74638</link.rule.ids></links><search><creatorcontrib>Bodlaender, Hans L.</creatorcontrib><creatorcontrib>Jaffke, Lars</creatorcontrib><creatorcontrib>Telle, Jan Arne</creatorcontrib><title>Typical Sequences Revisited — Computing Width Parameters of Graphs</title><title>Theory of computing systems</title><addtitle>Theory Comput Syst</addtitle><description>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.</description><subject>Algorithms</subject><subject>Computer Science</subject><subject>Dynamic programming</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Polynomials</subject><subject>Run time (computers)</subject><subject>Sequences</subject><subject>Special Issue on Theoretical Aspects of Computer Science (STACS 2020)</subject><subject>Theorems</subject><subject>Theory of Computation</subject><issn>1432-4350</issn><issn>1433-0490</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp9kEFOwzAQRS0EEqVwAVaWWBsmtpPYS1SgIFUCQRFLy0nGbao2CXaK1B2H4IScBEOQ2LGaGen9P1-fkNMEzhOA_CIAcC4Z8ITFWwATe2SUSCEYSA37PztnUqRwSI5CWEGEFMCIXM13XV3aNX3C1y02JQb6iG91qHus6Of7B520m27b182CvtRVv6QP1tsN9ugDbR2detstwzE5cHYd8OR3jsnzzfV8cstm99O7yeWMlSITPUNXYCUgcwmiqlyRps7JSuZFoRXoIq2wslpxJaUuLJZKl2mMKaTmQmvIpRiTs8G3821MG3qzare-iS8Nz_OM50pCFik-UKVvQ_DoTOfrjfU7k4D5bssMbZnYlvlpy4goEoMoRLhZoP-z_kf1BcKEbSo</recordid><startdate>20230201</startdate><enddate>20230201</enddate><creator>Bodlaender, Hans L.</creator><creator>Jaffke, Lars</creator><creator>Telle, Jan Arne</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>PYYUZ</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0002-9297-3330</orcidid><orcidid>https://orcid.org/0000-0003-4856-5863</orcidid></search><sort><creationdate>20230201</creationdate><title>Typical Sequences Revisited — Computing Width Parameters of Graphs</title><author>Bodlaender, Hans L. ; Jaffke, Lars ; Telle, Jan Arne</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Algorithms</topic><topic>Computer Science</topic><topic>Dynamic programming</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Polynomials</topic><topic>Run time (computers)</topic><topic>Sequences</topic><topic>Special Issue on Theoretical Aspects of Computer Science (STACS 2020)</topic><topic>Theorems</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bodlaender, Hans L.</creatorcontrib><creatorcontrib>Jaffke, Lars</creatorcontrib><creatorcontrib>Telle, Jan Arne</creatorcontrib><collection>Springer Open Access</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ProQuest_ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global (ProquesT)</collection><collection>Computing Database</collection><collection>ProQuest Science Journals</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>Theory of computing systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bodlaender, Hans L.</au><au>Jaffke, Lars</au><au>Telle, Jan Arne</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Typical Sequences Revisited — Computing Width Parameters of Graphs</atitle><jtitle>Theory of computing systems</jtitle><stitle>Theory Comput Syst</stitle><date>2023-02-01</date><risdate>2023</risdate><volume>67</volume><issue>1</issue><spage>52</spage><epage>88</epage><pages>52-88</pages><issn>1432-4350</issn><eissn>1433-0490</eissn><abstract>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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00224-021-10030-3</doi><tpages>37</tpages><orcidid>https://orcid.org/0000-0002-9297-3330</orcidid><orcidid>https://orcid.org/0000-0003-4856-5863</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1432-4350
ispartof Theory of computing systems, 2023-02, Vol.67 (1), p.52-88
issn 1432-4350
1433-0490
language eng
recordid cdi_proquest_journals_2776278406
source Springer Nature; ABI/INFORM Global (ProquesT); BSC - Ebsco (Business Source Ultimate)
subjects Algorithms
Computer Science
Dynamic programming
Graph theory
Graphs
Polynomials
Run time (computers)
Sequences
Special Issue on Theoretical Aspects of Computer Science (STACS 2020)
Theorems
Theory of Computation
title Typical Sequences Revisited — Computing Width Parameters of Graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-01T15%3A42%3A51IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Typical%20Sequences%20Revisited%20%E2%80%94%20Computing%20Width%20Parameters%20of%20Graphs&rft.jtitle=Theory%20of%20computing%20systems&rft.au=Bodlaender,%20Hans%20L.&rft.date=2023-02-01&rft.volume=67&rft.issue=1&rft.spage=52&rft.epage=88&rft.pages=52-88&rft.issn=1432-4350&rft.eissn=1433-0490&rft_id=info:doi/10.1007/s00224-021-10030-3&rft_dat=%3Cproquest_cross%3E2776278406%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-efbed306f1ee8dfb55ff4d47bb9809b5deda9828449baec89c500334923990743%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2776278406&rft_id=info:pmid/&rfr_iscdi=true