Still Life Theory
Cook (2003) shows that a still life pattern in Conway's Game of Life may be partitioned into two smaller still lifes if and only if an associated switch graph contains a regular cycle. As he shows, for switch graphs with at most three edges per vertex, this may be tested in polynomial time by repeatedly removing bridges (edges the removal of which disconnects the graph) and vertices at which all edges belong to a single partition until no more such simplifications may be performed. If the result is an empty graph, there is no regular cycle; otherwise, a regular cycle may be found in any remaining bridgeless component. The repeated search for bridges in this algorithm may be performed efficiently using a dynamic graph algorithm of Thorup (2000).
Similar bridge-removal techniques in the context of matching were previously considered by Gabow, Kaplan & Tarjan (1999).
Read more about this topic: Skew-symmetric Graph
Famous quotes containing the words life and/or theory:
“I began quite early in life to sense the thrill a girl attains in supplying money to a man.”
—Anita Loos (1894–1981)
“It is not enough for theory to describe and analyse, it must itself be an event in the universe it describes. In order to do this theory must partake of and become the acceleration of this logic. It must tear itself from all referents and take pride only in the future. Theory must operate on time at the cost of a deliberate distortion of present reality.”
—Jean Baudrillard (b. 1929)