Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Reachability Problems: An Update
verfasst von : Eric Allender
Erschienen in: Computation and Logic in the Real World
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
There has been a great deal of progress in the fifteen years that have elapsed since Wigderson published his survey on the complexity of the graph connectivity problem [Wig92]. Most significantly, Reingold solved the longstanding question of the complexity of the
s
-
t
connectivity problem in undirected graphs, showing that this is complete for logspace (L) [Rei05].
This survey talk will focus on some of the remaining open questions dealing with graph reachability problems. Particular attention will be paid to these topics:
Reachability in planar directed graphs (and more generally, in graphs of low genus) [ADR05, BTV07].
Reachability in different classes of grid graphs [ABC
+
06].
Reachability in mangroves [AL98].