Constructing Tree Decompositions of Graphs with Bounded Gonality
| Autor: | Bodlaender, Hans L., van Dobben de Bruyn, J., Gijswijt, D.C., Smit, Harry, Kim, Donghyun, Uma, R.N., Cai, Zhipeng, Lee, Dong Hoon |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Commutative Algebra
Constructive proof 010102 general mathematics 0102 computer and information sciences 01 natural sciences Tree decomposition Graph Combinatorics Treewidth Mathematics::Algebraic Geometry 010201 computation theory & mathematics Bounded function 0101 mathematics Time complexity Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030581497 COCOON Computing and Combinatorics: 26th International Conference, COCOON 2020, Proceedings Computing and Combinatorics |
| DOI: | 10.1007/978-3-030-58150-3_31 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|