All-pairs shortest paths with real weights in O(n3/log n) time

Timothy M. Chan

doi:10.1007/11534273_28

All-pairs shortest paths with real weights in O(n³/log n) time

Research output: Contribution to journal › Conference article › peer-review

Abstract

We describe an O(n³/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

Original language	English (US)
Pages (from-to)	318-324
Number of pages	7
Journal	Lecture Notes in Computer Science
Volume	3608
DOIs	https://doi.org/10.1007/11534273_28
State	Published - 2005
Externally published	Yes
Event	9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: Aug 15 2005 → Aug 17 2005

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/11534273_28

Library availability

Discover UIUC Full Text

Cite this

@article{23342fc1ea494064a7c924edead7ab9e,

title = "All-pairs shortest paths with real weights in O(n3/log n) time",

abstract = "We describe an O(n3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.",

author = "Chan, {Timothy M.}",

year = "2005",

doi = "10.1007/11534273_28",

language = "English (US)",

volume = "3608",

pages = "318--324",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

T1 - All-pairs shortest paths with real weights in O(n3/log n) time

AU - Chan, Timothy M.

PY - 2005

Y1 - 2005

N2 - We describe an O(n3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

AB - We describe an O(n3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

UR - http://www.scopus.com/inward/record.url?scp=26844516090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26844516090&partnerID=8YFLogxK

U2 - 10.1007/11534273_28

DO - 10.1007/11534273_28

M3 - Conference article

AN - SCOPUS:26844516090

SN - 0302-9743

VL - 3608

SP - 318

EP - 324

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 9th International Workshop on Algorithms and Data Structures, WADS 2005

Y2 - 15 August 2005 through 17 August 2005

ER -