Polynomial bound for a chip firing game on graphs. (English) Zbl 0652.68089

Summary: Björner, Lovász, and Shor have introduced a chip firing game on graphs. This paper proves a polynomial bound on the length of the game in terms of the number of vertices of the graph provided the length is finite. The obtained bound is best possible within a constant factor.


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C35 Extremal problems in graph theory
Full Text: DOI