Constructing tree decompositions of graphs with bounded gonality

Hans L. Bodlaender; Josse van Dobben de Bruyn; Dion Gijswijt; Harry Smit

doi:10.1007/s10878-021-00762-w

Constructing tree decompositions of graphs with bounded gonality

Hans L. Bodlaender, Josse van Dobben de Bruyn, Dion Gijswijt^*, Harry Smit

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

65 Downloads (Pure)

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.

Original language	English
Pages (from-to)	2681-2699
Number of pages	19
Journal	Journal of Combinatorial Optimization
Volume	44
Issue number	4
DOIs	https://doi.org/10.1007/s10878-021-00762-w
Publication status	Published - 2021

Keywords

Chip firing
Gonality
Tree decomposition

Access to Document

10.1007/s10878-021-00762-w

Bodlaender2021_Article_ConstructingTreeDecompositionsFinal published version, 502 KBLicence: CC BY

Cite this

@article{d86eba46c76549fd9b90393b33bb7270,

title = "Constructing tree decompositions of graphs with bounded gonality",

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.",

keywords = "Chip firing, Gonality, Tree decomposition",

author = "Bodlaender, {Hans L.} and {van Dobben de Bruyn}, Josse and Dion Gijswijt and Harry Smit",

year = "2021",

doi = "10.1007/s10878-021-00762-w",

language = "English",

volume = "44",

pages = "2681--2699",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Constructing tree decompositions of graphs with bounded gonality

AU - Bodlaender, Hans L.

AU - van Dobben de Bruyn, Josse

AU - Gijswijt, Dion

AU - Smit, Harry

PY - 2021

Y1 - 2021

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

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

KW - Chip firing

KW - Gonality

KW - Tree decomposition

UR - http://www.scopus.com/inward/record.url?scp=85111847989&partnerID=8YFLogxK

U2 - 10.1007/s10878-021-00762-w

DO - 10.1007/s10878-021-00762-w

M3 - Article

AN - SCOPUS:85111847989

SN - 1382-6905

VL - 44

SP - 2681

EP - 2699

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

Constructing tree decompositions of graphs with bounded gonality

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this