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:
“In our rhythm of earthly life we tire of light. We are glad when the day ends, when the play ends; and ecstasy is too much pain.”
—T.S. (Thomas Stearns)
“The theory seems to be that so long as a man is a failure he is one of God’s chillun, but that as soon as he has any luck he owes it to the Devil.”
—H.L. (Henry Lewis)