Computing graph gonality is hard
From MaRDI portal
Publication:2004086
DOI10.1016/j.dam.2020.08.013zbMath1450.05088arXiv1504.06713OpenAlexW3080153597MaRDI QIDQ2004086
Harry Smit, Marieke van der Wegen, Dion C. Gijswijt
Publication date: 14 October 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.06713
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Discrete and metric divisorial gonality can be different ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Multiplicity-free gonality on graphs ⋮ Graphs of scramble number two ⋮ On the gonality of Cartesian products of graphs ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Stable divisorial gonality is in NP ⋮ A new lower bound on graph gonality ⋮ Gonality Sequences of Graphs ⋮ On the scramble number of graphs ⋮ Computing zeta functions of algebraic curves using Harvey's trace formula
Uses Software
Cites Work
- Unnamed Item
- Computational aspects of gonal maps and radical parametrization of curves
- A tropical proof of the Brill-Noether theorem
- Chip-firing games on graphs
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- Chip-firing and the critical group of a graph
- Curves with infinitely many points of fixed degree
- The Magma algebra system. I: The user language
- Some APX-completeness results for cubic graphs
- Chip-firing games, potential theory on graphs, and spanning trees
- Tropical hyperelliptic curves
- Lifting harmonic morphisms. II: Tropical curves and metrized complexes
- Treewidth is a lower bound on graph gonality
- A combinatorial Li-Yau inequality and rational points on curves
- Rank of divisors on tropical curves
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Special divisors on marked chains of cycles
- The chip-firing game
- Harmonic Morphisms and Hyperelliptic Graphs
- A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
- Sparse Graphs of High Gonality
- Stable gonality is computable
- Recognizing hyperelliptic graphs in polynomial time
This page was built for publication: Computing graph gonality is hard