Geodesic
Stable gonality is computable
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2019_21_1_a10,
     author = {Koerkamp, Ragnar Groot and van der Wegen, Marieke},
     title = {Stable gonality is computable},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2019},
     volume = {21},
     number = {1},
     doi = {10.23638/DMTCS-21-1-10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-10/}
}
TY  - JOUR
AU  - Koerkamp, Ragnar Groot
AU  - van der Wegen, Marieke
TI  - Stable gonality is computable
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-10/
DO  - 10.23638/DMTCS-21-1-10
LA  - en
ID  - DMTCS_2019_21_1_a10
ER  - 
%0 Journal Article
%A Koerkamp, Ragnar Groot
%A van der Wegen, Marieke
%T Stable gonality is computable
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-10/
%R 10.23638/DMTCS-21-1-10
%G en
%F DMTCS_2019_21_1_a10
Koerkamp, Ragnar Groot; van der Wegen, Marieke. Stable gonality is computable. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi: 10.23638/DMTCS-21-1-10

Cité par Sources :