Reachability problems: An update

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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].

Original languageEnglish (US)
Title of host publicationComputation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings
Number of pages3
StatePublished - 2007
Event3rd Conference on Computability in Europe, CiE 2007 - Siena, Italy
Duration: Jun 18 2007Jun 23 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4497 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Conference on Computability in Europe, CiE 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Reachability problems: An update'. Together they form a unique fingerprint.

Cite this