Reachability problems: An update

Eric Allender

doi:10.1007/978-3-540-73001-9_3

Reachability problems: An update

Eric Allender

School of Arts and Sciences, Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings
Pages	25-27
Number of pages	3
DOIs	https://doi.org/10.1007/978-3-540-73001-9_3
State	Published - 2007
Event	3rd Conference on Computability in Europe, CiE 2007 - Siena, Italy Duration: Jun 18 2007 → Jun 23 2007

Publication series

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

Other

Other	3rd Conference on Computability in Europe, CiE 2007
Country/Territory	Italy
City	Siena
Period	6/18/07 → 6/23/07

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-73001-9_3

Cite this

Allender, E. (2007). Reachability problems: An update. In Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings (pp. 25-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4497 LNCS). https://doi.org/10.1007/978-3-540-73001-9_3

@inproceedings{85927ced9dcd41b09bc9c96f0665b6fe,

title = "Reachability problems: An update",

abstract = "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].",

author = "Eric Allender",

year = "2007",

doi = "10.1007/978-3-540-73001-9_3",

language = "English (US)",

isbn = "9783540730002",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "25--27",

booktitle = "Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings",

note = "3rd Conference on Computability in Europe, CiE 2007 ; Conference date: 18-06-2007 Through 23-06-2007",

}

Allender, E 2007, Reachability problems: An update. in Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4497 LNCS, pp. 25-27, 3rd Conference on Computability in Europe, CiE 2007, Siena, Italy, 6/18/07. https://doi.org/10.1007/978-3-540-73001-9_3

Reachability problems: An update. / Allender, Eric.
Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings. 2007. p. 25-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4497 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Reachability problems

T2 - 3rd Conference on Computability in Europe, CiE 2007

AU - Allender, Eric

PY - 2007

Y1 - 2007

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

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

UR - http://www.scopus.com/inward/record.url?scp=38149136428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149136428&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73001-9_3

DO - 10.1007/978-3-540-73001-9_3

M3 - Conference contribution

AN - SCOPUS:38149136428

SN - 9783540730002

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 27

BT - Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings

Y2 - 18 June 2007 through 23 June 2007

ER -

Reachability problems: An update

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this