Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-106 | 31st May 2018 13:17

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous Logspace

RSS-Feed




Revision #1
Authors: Chetan Gupta, Vimalraj Sharma, Raghunath Tewari
Accepted on: 31st May 2018 13:17
Downloads: 1044
Keywords: 


Abstract:

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices
$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous
logarithmic space.



Changes to previous version:

There was a small mistake in title of the paper. Term "Logspace" was missing.


Paper:

TR18-106 | 30th May 2018 14:14

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous





TR18-106
Authors: Chetan Gupta, Vimalraj Sharma, Raghunath Tewari
Publication: 30th May 2018 21:28
Downloads: 818
Keywords: 


Abstract:

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices
$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous
logarithmic space.



ISSN 1433-8092 | Imprint