Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem

by: Tadao Takaoka

(1995), pp. 323-343.

View FullText article

CiteSeer (at Penn State), CiteSeer (at MIT), CiteSeer (at Zurich), CiteSeer (at Singapore)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

jmarcelino

Find related articles with these CiteULike tags

no-tag

Abstract

. In this paper we give three sub-cubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log 2 n) time with O(n ffi p log n) processors where = 2:688 on an EREW-PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with non-negative general costs (real numbers) in O(log 2 n) time with o(n 3 ...

@inproceedings{citeulike:1873794, abstract = {. In this paper we give three sub-cubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log 2 n) time with O(n ffi p log n) processors where = 2:688 on an EREW-PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with non-negative general costs (real numbers) in O(log 2 n) time with o(n 3 ...}, author = {Takaoka, Tadao }, booktitle = {Workshop on Graph-Theoretic Concepts in Computer Science}, citeulike-article-id = {1873794}, pages = {323--343}, posted-at = {2007-11-06 12:35:10}, priority = {2}, title = {Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem}, url = {http://citeseer.ist.psu.edu/357974.html}, year = {1995} }

RIS record

TY - CONF ID - citeulike:1873794 L3 - citeulike-article-id:1873794 TI - Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem T2 - Workshop on Graph-Theoretic Concepts in Computer Science SP - 323 EP - 343 N2 - . In this paper we give three sub-cubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log 2 n) time with O(n ffi p log n) processors where = 2:688 on an EREW-PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with non-negative general costs (real numbers) in O(log 2 n) time with o(n 3 ... AU - Takaoka, Tadao PY - 1995/// UR - http://citeseer.ist.psu.edu/357974.html ER -

RIS BibTeX