Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GRAPH GENUS:
Reports tagged with graph genus:
TR04-108 | 24th November 2004
Eric Allender, Samir Datta, Sambuddha Roy

Topology inside NC^1

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.
We consider other generalizations of ... more >>>


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




ISSN 1433-8092 | Imprint