Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ACYCLIC:
Reports tagged with acyclic:
TR09-049 | 5th May 2009
Derrick Stolee, Chris Bourke, Vinodchandran Variyam

A log-space algorithm for reachability in planar DAGs with few sources

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>




ISSN 1433-8092 | Imprint