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:
“Clever people seem not to feel the natural pleasure of bewilderment, and are always answering questions when the chief relish of a life is to go on asking them.”
—Frank Moore Colby (1865–1925)
“... the first reason for psychology’s failure to understand what people are and how they act, is that clinicians and psychiatrists, who are generally the theoreticians on these matters, have essentially made up myths without any evidence to support them; the second reason for psychology’s failure is that personality theory has looked for inner traits when it should have been looking for social context.”
—Naomi Weisstein (b. 1939)