Constructing Tree Decompositions of Graphs with Bounded Gonality

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

doi:10.1007/978-3-030-58150-3_31

Constructing Tree Decompositions of Graphs with Bounded Gonality

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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
Title of host publication	Computing and Combinatorics
Subtitle of host publication	26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings
Editors	Donghyun Kim, R. N. Uma, Zhipeng Cai, Dong Hoon Lee
Place of Publication	Cham
Publisher	Springer
Pages	384-396
Number of pages	13
ISBN (Electronic)	978-3-030-58150-3
ISBN (Print)	978-3-030-58149-7
DOIs	https://doi.org/10.1007/978-3-030-58150-3_31
Publication status	Published - 2020

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12273
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-030-58150-3_31

978-3-030-58150-3_31Final published version, 355 KBLicence: Taverne

Cite this

Bodlaender, H. L., Bruyn, J. V. D. D., Gijswijt, D., & Smit, H. (2020). Constructing Tree Decompositions of Graphs with Bounded Gonality. In D. Kim, R. N. Uma, Z. Cai, & D. H. Lee (Eds.), Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings (pp. 384-396). ( Lecture Notes in Computer Science ; Vol. 12273). Springer. https://doi.org/10.1007/978-3-030-58150-3_31

Bodlaender, Hans L. ; Bruyn, Josse van Dobben de ; Gijswijt, Dion et al. / Constructing Tree Decompositions of Graphs with Bounded Gonality. Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. editor / Donghyun Kim ; R. N. Uma ; Zhipeng Cai ; Dong Hoon Lee. Cham : Springer, 2020. pp. 384-396 ( Lecture Notes in Computer Science ).

@inproceedings{538438346c52401aafc16deb751eb324,

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

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

year = "2020",

doi = "10.1007/978-3-030-58150-3_31",

language = "English",

isbn = "978-3-030-58149-7",

series = " Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "384--396",

editor = "Donghyun Kim and Uma, {R. N.} and Zhipeng Cai and Lee, {Dong Hoon}",

booktitle = "Computing and Combinatorics",

}

Bodlaender, HL, Bruyn, JVDD, Gijswijt, D & Smit, H 2020, Constructing Tree Decompositions of Graphs with Bounded Gonality. in D Kim, RN Uma, Z Cai & DH Lee (eds), Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. Lecture Notes in Computer Science , vol. 12273, Springer, Cham, pp. 384-396. https://doi.org/10.1007/978-3-030-58150-3_31

Constructing Tree Decompositions of Graphs with Bounded Gonality. / Bodlaender, Hans L.; Bruyn, Josse van Dobben de; Gijswijt, Dion et al.
Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. ed. / Donghyun Kim; R. N. Uma; Zhipeng Cai; Dong Hoon Lee. Cham: Springer, 2020. p. 384-396 ( Lecture Notes in Computer Science ; Vol. 12273).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Constructing Tree Decompositions of Graphs with Bounded Gonality

AU - Bodlaender, Hans L.

AU - Bruyn, Josse van Dobben de

AU - Gijswijt, Dion

AU - Smit, Harry

PY - 2020

Y1 - 2020

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.

U2 - 10.1007/978-3-030-58150-3_31

DO - 10.1007/978-3-030-58150-3_31

M3 - Conference contribution

SN - 978-3-030-58149-7

T3 - Lecture Notes in Computer Science

SP - 384

EP - 396

BT - Computing and Combinatorics

A2 - Kim, Donghyun

A2 - Uma, R. N.

A2 - Cai, Zhipeng

A2 - Lee, Dong Hoon

PB - Springer

CY - Cham

ER -

Bodlaender HL, Bruyn JVDD, Gijswijt D, Smit H. Constructing Tree Decompositions of Graphs with Bounded Gonality. In Kim D, Uma RN, Cai Z, Lee DH, editors, Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. Cham: Springer. 2020. p. 384-396. ( Lecture Notes in Computer Science ). doi: 10.1007/978-3-030-58150-3_31

Constructing Tree Decompositions of Graphs with Bounded Gonality

Abstract

Publication series

Access to Document

Fingerprint

Cite this