Constructing tree decompositions of graphs with bounded gonality

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k , when an effective divisor of degree k that reaches all vertices is given. We al...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2022-11, Vol.44 (4), p.2681-2699
Main Authors: Bodlaender, Hans L., van Dobben de Bruyn, Josse, Gijswijt, Dion, Smit, Harry
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Combinatorics
Convex and Discrete Geometry
Decomposition
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Polynomials
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c314t-9e6c8d27a2eb40350a5b2d7397c93ce1a5d948cf5111208afa9dfedd12a41fd03
container_end_page 2699
container_issue 4
container_start_page 2681
container_title Journal of combinatorial optimization
container_volume 44
creator Bodlaender, Hans L.
van Dobben de Bruyn, Josse
Gijswijt, Dion
Smit, Harry
description In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k , when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.
doi_str_mv 10.1007/s10878-021-00762-w
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2724907522</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2724907522</sourcerecordid><originalsourceid>FETCH-LOGICAL-c314t-9e6c8d27a2eb40350a5b2d7397c93ce1a5d948cf5111208afa9dfedd12a41fd03</originalsourceid><addsrcrecordid>eNp9kE9LxDAQxYMouK5-AU8Fz9FJ0jbJTVn8Bwte9ByySdrtstvUJKXstzdawZunecO89xh-CF0TuCUA_C4SEFxgoATntaZ4OkELUnGGqRD1adZMUFxLqM7RRYw7AMi6XKD7le9jCqNJXd8WKThXWGf8YfCxS12-Fb4p2qCHbSymLm2LjR9762zR-l7vu3S8RGeN3kd39TuX6OPp8X31gtdvz6-rhzU2jJQJS1cbYSnX1G1KYBXoakMtZ5IbyYwjurKyFKapCCEUhG60tI2zllBdksYCW6KbuXcI_nN0MamdH0P-ISrKaSmBV5RmF51dJvgYg2vUELqDDkdFQH2TUjMplUmpH1JqyiE2h2I2960Lf9X_pL4AdsZtEQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2724907522</pqid></control><display><type>article</type><title>Constructing tree decompositions of graphs with bounded gonality</title><source>Springer Nature</source><creator>Bodlaender, Hans L. ; van Dobben de Bruyn, Josse ; Gijswijt, Dion ; Smit, Harry</creator><creatorcontrib>Bodlaender, Hans L. ; van Dobben de Bruyn, Josse ; Gijswijt, Dion ; Smit, Harry</creatorcontrib><description>In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k , when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.</description><identifier>ISSN: 1382-6905</identifier><identifier>EISSN: 1573-2886</identifier><identifier>DOI: 10.1007/s10878-021-00762-w</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Apexes ; Combinatorics ; Convex and Discrete Geometry ; Decomposition ; Mathematical Modeling and Industrial Mathematics ; Mathematics ; Mathematics and Statistics ; Operations Research/Decision Theory ; Optimization ; Polynomials ; Theory of Computation</subject><ispartof>Journal of combinatorial optimization, 2022-11, Vol.44 (4), p.2681-2699</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><cites>FETCH-LOGICAL-c314t-9e6c8d27a2eb40350a5b2d7397c93ce1a5d948cf5111208afa9dfedd12a41fd03</cites><orcidid>0000-0003-0734-4511</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Bodlaender, Hans L.</creatorcontrib><creatorcontrib>van Dobben de Bruyn, Josse</creatorcontrib><creatorcontrib>Gijswijt, Dion</creatorcontrib><creatorcontrib>Smit, Harry</creatorcontrib><title>Constructing tree decompositions of graphs with bounded gonality</title><title>Journal of combinatorial optimization</title><addtitle>J Comb Optim</addtitle><description>In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k , when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.</description><subject>Algorithms</subject><subject>Apexes</subject><subject>Combinatorics</subject><subject>Convex and Discrete Geometry</subject><subject>Decomposition</subject><subject>Mathematical Modeling and Industrial Mathematics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Polynomials</subject><subject>Theory of Computation</subject><issn>1382-6905</issn><issn>1573-2886</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9kE9LxDAQxYMouK5-AU8Fz9FJ0jbJTVn8Bwte9ByySdrtstvUJKXstzdawZunecO89xh-CF0TuCUA_C4SEFxgoATntaZ4OkELUnGGqRD1adZMUFxLqM7RRYw7AMi6XKD7le9jCqNJXd8WKThXWGf8YfCxS12-Fb4p2qCHbSymLm2LjR9762zR-l7vu3S8RGeN3kd39TuX6OPp8X31gtdvz6-rhzU2jJQJS1cbYSnX1G1KYBXoakMtZ5IbyYwjurKyFKapCCEUhG60tI2zllBdksYCW6KbuXcI_nN0MamdH0P-ISrKaSmBV5RmF51dJvgYg2vUELqDDkdFQH2TUjMplUmpH1JqyiE2h2I2960Lf9X_pL4AdsZtEQ</recordid><startdate>20221101</startdate><enddate>20221101</enddate><creator>Bodlaender, Hans L.</creator><creator>van Dobben de Bruyn, Josse</creator><creator>Gijswijt, Dion</creator><creator>Smit, Harry</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0003-0734-4511</orcidid></search><sort><creationdate>20221101</creationdate><title>Constructing tree decompositions of graphs with bounded gonality</title><author>Bodlaender, Hans L. ; van Dobben de Bruyn, Josse ; Gijswijt, Dion ; Smit, Harry</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c314t-9e6c8d27a2eb40350a5b2d7397c93ce1a5d948cf5111208afa9dfedd12a41fd03</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Apexes</topic><topic>Combinatorics</topic><topic>Convex and Discrete Geometry</topic><topic>Decomposition</topic><topic>Mathematical Modeling and Industrial Mathematics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Polynomials</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bodlaender, Hans L.</creatorcontrib><creatorcontrib>van Dobben de Bruyn, Josse</creatorcontrib><creatorcontrib>Gijswijt, Dion</creatorcontrib><creatorcontrib>Smit, Harry</creatorcontrib><collection>SpringerOpen</collection><collection>CrossRef</collection><jtitle>Journal of combinatorial optimization</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bodlaender, Hans L.</au><au>van Dobben de Bruyn, Josse</au><au>Gijswijt, Dion</au><au>Smit, Harry</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Constructing tree decompositions of graphs with bounded gonality</atitle><jtitle>Journal of combinatorial optimization</jtitle><stitle>J Comb Optim</stitle><date>2022-11-01</date><risdate>2022</risdate><volume>44</volume><issue>4</issue><spage>2681</spage><epage>2699</epage><pages>2681-2699</pages><issn>1382-6905</issn><eissn>1573-2886</eissn><abstract>In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k , when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10878-021-00762-w</doi><tpages>19</tpages><orcidid>https://orcid.org/0000-0003-0734-4511</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1382-6905
ispartof Journal of combinatorial optimization, 2022-11, Vol.44 (4), p.2681-2699
issn 1382-6905
1573-2886
language eng
recordid cdi_proquest_journals_2724907522
source Springer Nature
subjects Algorithms
Apexes
Combinatorics
Convex and Discrete Geometry
Decomposition
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Polynomials
Theory of Computation
title Constructing tree decompositions of graphs with bounded gonality
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-01T14%3A46%3A57IST&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=Constructing%20tree%20decompositions%20of%20graphs%20with%20bounded%20gonality&rft.jtitle=Journal%20of%20combinatorial%20optimization&rft.au=Bodlaender,%20Hans%20L.&rft.date=2022-11-01&rft.volume=44&rft.issue=4&rft.spage=2681&rft.epage=2699&rft.pages=2681-2699&rft.issn=1382-6905&rft.eissn=1573-2886&rft_id=info:doi/10.1007/s10878-021-00762-w&rft_dat=%3Cproquest_cross%3E2724907522%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c314t-9e6c8d27a2eb40350a5b2d7397c93ce1a5d948cf5111208afa9dfedd12a41fd03%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2724907522&rft_id=info:pmid/&rfr_iscdi=true