An O(n3 log log n/log n) time algorithm for the all-pairs shortest path problem

被引：22

作者：

Takaoka, T ^{[1
]}

机构：

[1] Univ Canterbury, Dept Comp Sci, Christchurch 1, New Zealand

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 96卷 / 05期

关键词：

graph algorithms; shortest path; divide and conquer;

D O I：

10.1016/j.ipl.2005.08.008

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper achieves O(n(3) log log n/ log n) time for the all pairs shortest path problem on the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bits are allowed. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：155 / 161

页数：7

共 50 条

[1] An O(n3(log log n/log n)5/4) time algorithm for all pairs shortest path
Han, Yijie
ALGORITHMICA, 2008, 51 (04) : 428 - 434
[2] An O(n3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path
Yijie Han
Algorithmica, 2008, 51 : 428 - 434
[3] 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
[4] All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time
Timothy M. Chan
Algorithmica, 2008, 50 : 236 - 243
[5] All-pairs shortest paths with real weights in O(n3/log n) time
Chan, TM
ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS, 2005, 3608 : 318 - 324
[6] 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
[7] 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
[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 →