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:
“Everything in life that we really accept undergoes a change. So suffering must become Love. That is the mystery.”
—Katherine Mansfield (1888–1923)
“No theory is good unless it permits, not rest, but the greatest work. No theory is good except on condition that one use it to go on beyond.”
—André Gide (1869–1951)