On the complexity of the chip-firing reachability problem

DOI10.1090/proc/13498zbMath1365.05164arXiv1507.03209OpenAlexW2241132100MaRDI QIDQ5270136

Viktor Kiss, Lilla Tóthmérész, Bálint Hujter

Publication date: 22 June 2017

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.03209

zbMATH Keywords

computational complexitychip-firing game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

Abelian networks IV. Dynamics of nonhalting networks ⋮ Chip-firing based methods in the Riemann-Roch theory of directed graphs ⋮ Algorithmic aspects of rotor-routing and the notion of linear equivalence ⋮ Abelian Logic Gates ⋮ Rotor-routing reachability is easy, chip-firing reachability is hard

Cites Work

• Chip-firing games on directed graphs
• Chip-firing games on graphs
• Geometric algorithms and combinatorial optimization
• Treewidth is a lower bound on graph gonality
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• CoEulerian graphs
• Abelian Networks I. Foundations and Examples
• Chip-Firing and Rotor-Routing on Directed Graphs

This page was built for publication: On the complexity of the chip-firing reachability problem