Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-99-09 August 1999

Abstract

Algorithmic aspects of a chip-firing game on a graph introduced by Biggs are studied. This variant of the chip-firing game, called the dollar game, has the properties that every starting configuration leads to a so-called critical configuration. The set of critical configuration has many interesting properties. In this paper is is proved that the number of steps needed to reach a critical configuration is polynomial in the number of edges of the graph and the number of chips in the starting configuration, but not necessarily in the size of the input. An alternative algorithm is also described and analysed.

A compressed (gzip) PostScript file (115 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-99-09, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html