An Efficient Algorithm for the Detection of Eden
David J. Warne*
Ross F. Hayward
School of Electrical Engineering and Computer Science
Queensland University of Technology
Brisbane, Queensland 4001, Australia
*david.warne@qut.edu.au
Neil A. Kelson
High Performance Computing and Research Support
Queensland University of Technology
Brisbane, Queensland 4001, Australia
Dann G. Mallet
School of Mathematical Sciences
Queensland University of Technology
Brisbane, Queensland 4001, Australia
Abstract
In this paper, a polynomial time algorithm is presented for solving the Eden problem for graph cellular automata. The algorithm is based on our neighborhood elimination operation, which removes local neighborhood configurations that cannot be used in a preimage of the given configuration. This paper presents a detailed derivation of our algorithm from first principles, and a detailed complexity and accuracy analysis is also given. In the case of time complexity, it is shown that the average-case time complexity of the algorithm is 
, and the best and worst cases are 
and 
, respectively. This represents a vast improvement in the upper bound over current methods, without compromising average-case performance.
