|
In this paper we address the chip-firing halting problem for undirected multigraphs. We give a polynomial algorithm for deciding the halting problem in the special case when the number of chips in the distribution is equal to the sum of the edge multiplicities of the graph. The key part of our algorithm uses convex cost flow optimization to give an efficient algorithmic proof of a theorem of An, Baker, Kuperberg and Shokrieh; improving a previous algorithm of Backman.
Bibtex entry:
| AUTHOR | = | {Hujter, B{\'a}lint}, |
| TITLE | = | {The chip-firing halting problem for multigraphs and convex cost flows}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2017}, |
| NUMBER | = | {TR-2017-01} |