Topic summary
Graph connectivity
Extracted from the Wikipedia article Connectivity (graph theory).
Computational aspects
In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Hence, undirected graph connectivity may be solved in O(log n) space.