An O(n3(log log n/log n)5/4) time algorithm for all pairs shortest path

被引：17

作者：

Han, Yijie ^{[1
]}

机构：

[1] Univ Missouri, Sch Comp & Engn, Kansas City, MO 64110 USA

来源：

ALGORITHMICA | 2008年 / 51卷 / 04期

基金：

美国国家科学基金会;

关键词：

algorithms; complexity; graph algorithms; shortest path;

D O I：

10.1007/s00453-007-9063-0

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an O(n(3)(log log n/log n)(5/4)) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n(3)/log n) time.

引用

页码：428 / 434

页数：7

共 50 条

[1] An O(n3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path
Yijie Han
Algorithmica, 2008, 51 : 428 - 434
[2] An O(n3(log log n/log n)5/4) time algorithm for all pairs shortest paths
Han, Yijie
ALGORITHMS - ESA 2006, PROCEEDINGS, 2006, 4168 : 411 - 417
[3] An O(n3 log log n/log n) time algorithm for the all-pairs shortest path problem
Takaoka, T
INFORMATION PROCESSING LETTERS, 2005, 96 (05) : 155 - 161
[4] An O(n(3) log log n/log(2) n) time algorithm for all pairs shortest paths
Han, Yijie
Takaoka, Tadao
JOURNAL OF DISCRETE ALGORITHMS, 2016, 38-41 : 9 - 19
[5] A note of an O(n3/log n) time algorithm for all pairs shortest paths
Han, Yijie
INFORMATION PROCESSING LETTERS, 2008, 105 (03) : 114 - 116
[6] All-pairs shortest paths with real weights in O(n3/log n) time
Chan, TM
ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS, 2005, 3608 : 318 - 324
[7] All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time
Timothy M. Chan
Algorithmica, 2008, 50 : 236 - 243
[8] A simplified algorithm for the all pairs shortest path problem with O(n2 log n) expected time
Takaoka, Tadao
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (02) : 326 - 337
[9] A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n2 log n) Expected Time
Takaoka, Tadao
Hashim, Mashitoh
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT II, 2010, 6509 : 195 - 206
[10] A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)
Poli, A.
Journal of Symbolic Computation, 19 (04):

← 1 2 3 4 5 →