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

Tardos, Gábor

SIAM J. Discrete Math. 1, No. 3, 397-398 (1988).

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.

MSC:

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

Keywords:

polynomial time; chip firing game on graphs