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

Discrete Mathematics and Optimization

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

1 Citation (Scopus)

50 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
Title of host publication	Computing and Combinatorics
Subtitle of host publication	26th International Conference, COCOON 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
Event	26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, United States Duration: 29 Aug 2020 → 31 Aug 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	12273
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on Computing and Combinatorics, COCOON 2020
Country/Territory	United States
City	Atlanta
Period	29/08/20 → 31/08/20

Bibliographical note

Accepted author manuscript

Access to Document

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

main_conference_version_for_pureAccepted author manuscript, 421 KB

Cite this

Bodlaender, H. L., van Dobben de Bruyn, J., 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, Proceedings (pp. 384-396). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12273 ). Springer. https://doi.org/10.1007/978-3-030-58150-3_31

Bodlaender, Hans L. ; van Dobben de Bruyn, Josse ; Gijswijt, Dion et al. / Constructing tree decompositions of graphs with bounded gonality. Computing and Combinatorics : 26th International Conference, COCOON 2020, Proceedings. editor / Donghyun Kim ; R.N. Uma ; Zhipeng Cai ; Dong Hoon Lee. Cham : Springer, 2020. pp. 384-396 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8a8ff540209f477ab8490e5dc402fa33,

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 {van Dobben de Bruyn}, Josse and Dion Gijswijt and Harry Smit",

note = "Accepted author manuscript; 26th International Conference on Computing and Combinatorics, COCOON 2020 ; Conference date: 29-08-2020 Through 31-08-2020",

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "384--396",

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

booktitle = "Computing and Combinatorics",

}

Bodlaender, HL, van Dobben de Bruyn, J , 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, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12273 , Springer, Cham, pp. 384-396, 26th International Conference on Computing and Combinatorics, COCOON 2020, Atlanta, United States, 29/08/20. https://doi.org/10.1007/978-3-030-58150-3_31

Constructing tree decompositions of graphs with bounded gonality. / Bodlaender, Hans L.; van Dobben de Bruyn, Josse ; Gijswijt, Dion et al.
Computing and Combinatorics : 26th International Conference, COCOON 2020, Proceedings. ed. / Donghyun Kim; R.N. Uma; Zhipeng Cai; Dong Hoon Lee. Cham: Springer, 2020. p. 384-396 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12273 ).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

N1 - Accepted author manuscript

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.

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

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

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

M3 - Conference contribution

AN - SCOPUS:85091109020

SN - 978-3-030-58149-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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

T2 - 26th International Conference on Computing and Combinatorics, COCOON 2020

Y2 - 29 August 2020 through 31 August 2020

ER -

Bodlaender HL, van Dobben de Bruyn J , 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, Proceedings. Cham: Springer. 2020. p. 384-396. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-58150-3_31

Constructing tree decompositions of graphs with bounded gonality

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this