Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-003 | 2nd December 2015 01:37

On the logspace shortest path problem

RSS-Feed




TR16-003
Authors: Boris Brimkov, Illya Hicks
Publication: 22nd January 2016 12:35
Downloads: 3898
Keywords: 


Abstract:

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 degree and biconnected component size, which does not rely on an oracle. The asymptotic time-space product of this algorithm is the best possible among all shortest path algorithms.



ISSN 1433-8092 | Imprint