Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph reachability:
TR05-148 | 6th December 2005
Eric Allender, Samir Datta, Sambuddha Roy

The Directed Planar Reachability Problem

Revisions: 1

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

TR14-008 | 20th January 2014
N. V. Vinodchandran

Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

TR17-052 | 19th March 2017
Dieter van Melkebeek, Gautam Prakriya

Derandomizing Isolation in Space-Bounded Settings

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

ISSN 1433-8092 | Imprint