ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > 3}-FREE:
Reports tagged with 3}-free:
TR09-029 | 3rd April 2009
Fabian Wagner, Thomas Thierauf

Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1
We show that the reachability problem for directed graphs that are either K_{3,3}-free or K_5-free is in unambiguous log-space, UL \cap coUL. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in UL \cap coUL. Our algorithm decomposes the graphs ... more >>>



ISSN 1433-8092 | Imprint