Stable gonality is computable
Stable gonality is a multigraph parameter that measures the complexity of a graph. It is defined using maps to trees. Those maps, in some sense, divide the edges equally over the edges of the tree; stable gonality asks for the map with the minimum number of edges mapped to each edge of the tree. Thi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Jezik: | English |
| Izdano: |
Discrete Mathematics & Theoretical Computer Science
2019-06-01
|
| Serija: | Discrete Mathematics & Theoretical Computer Science |
| Teme: | |
| Online dostop: | https://dmtcs.episciences.org/4931/pdf |
| _version_ | 1827323776355794944 |
|---|---|
| author | Ragnar Groot Koerkamp Marieke van der Wegen |
| author_facet | Ragnar Groot Koerkamp Marieke van der Wegen |
| author_sort | Ragnar Groot Koerkamp |
| collection | DOAJ |
| description | Stable gonality is a multigraph parameter that measures the complexity of a
graph. It is defined using maps to trees. Those maps, in some sense, divide the
edges equally over the edges of the tree; stable gonality asks for the map with
the minimum number of edges mapped to each edge of the tree. This parameter is
related to treewidth, but unlike treewidth, it distinguishes multigraphs from
their underlying simple graphs. Stable gonality is relevant for problems in
number theory. In this paper, we show that deciding whether the stable gonality
of a given graph is at most a given integer $k$ belongs to the class NP, and we
give an algorithm that computes the stable gonality of a graph in
$O((1.33n)^nm^m \text{poly}(n,m))$ time. |
| first_indexed | 2024-04-25T01:57:56Z |
| format | Article |
| id | doaj.art-db83f61672e6437c94e66bae01a6c07f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:56Z |
| publishDate | 2019-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-db83f61672e6437c94e66bae01a6c07f2024-03-07T15:37:58ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-06-01vol. 21 no. 1, ICGT 201810.23638/DMTCS-21-1-104931Stable gonality is computableRagnar Groot KoerkampMarieke van der WegenStable gonality is a multigraph parameter that measures the complexity of a graph. It is defined using maps to trees. Those maps, in some sense, divide the edges equally over the edges of the tree; stable gonality asks for the map with the minimum number of edges mapped to each edge of the tree. This parameter is related to treewidth, but unlike treewidth, it distinguishes multigraphs from their underlying simple graphs. Stable gonality is relevant for problems in number theory. In this paper, we show that deciding whether the stable gonality of a given graph is at most a given integer $k$ belongs to the class NP, and we give an algorithm that computes the stable gonality of a graph in $O((1.33n)^nm^m \text{poly}(n,m))$ time.https://dmtcs.episciences.org/4931/pdfcomputer science - discrete mathematicscomputer science - data structures and algorithmsmathematics - combinatoricsmathematics - number theory |
| spellingShingle | Ragnar Groot Koerkamp Marieke van der Wegen Stable gonality is computable Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics computer science - data structures and algorithms mathematics - combinatorics mathematics - number theory |
| title | Stable gonality is computable |
| title_full | Stable gonality is computable |
| title_fullStr | Stable gonality is computable |
| title_full_unstemmed | Stable gonality is computable |
| title_short | Stable gonality is computable |
| title_sort | stable gonality is computable |
| topic | computer science - discrete mathematics computer science - data structures and algorithms mathematics - combinatorics mathematics - number theory |
| url | https://dmtcs.episciences.org/4931/pdf |
| work_keys_str_mv | AT ragnargrootkoerkamp stablegonalityiscomputable AT mariekevanderwegen stablegonalityiscomputable |