Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ILLYA HICKS:
All reports by Author Illya Hicks:

TR16-003 | 2nd December 2015
Boris Brimkov, Illya Hicks

On the logspace shortest path problem

In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex ... more >>>




ISSN 1433-8092 | Imprint