Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOUNDED GENUS GRAPH:
Reports tagged with bounded genus graph:
TR09-050 | 28th May 2009
Jan Kyncl, Tomas Vyskocil

Logspace reduction of directed reachability for bounded genus graphs to the planar case

Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G. Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an ... more >>>




ISSN 1433-8092 | Imprint