An O(n3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path

被引：0
|
作者：
Yijie Han
机构：
[1] University of Missouri at Kansas City,School of Computing and Engineering
来源：
Algorithmica | 2008年 / 51卷
关键词：
Algorithms; Complexity; Graph algorithms; Shortest path;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We present an O(n3(log log n/log n)5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n3/log n) time.
引用
收藏
页码：428 / 434
页数：6
相关论文
共 50 条
  • [11] An O(n log n) Shortest Path Algorithm Based on Delaunay Triangulation
    Jan, Gene Eu
    Sun, Chi-Chia
    Tsai, Wei Chun
    Lin, Ting-Hsiang
    IEEE-ASME TRANSACTIONS ON MECHATRONICS, 2014, 19 (02) : 660 - 666
  • [12] Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n/log log n) Time
    Mozes, Shay
    Wulff-Nilsen, Christian
    ALGORITHMS-ESA 2010, PT II, 2010, 6347 : 206 - +
  • [13] A SHORTEST-PATH ALGORITHM WITH EXPECTED TIME O(N2 LOG N LOGSTAR N)
    BLONIARZ, PA
    SIAM JOURNAL ON COMPUTING, 1983, 12 (03) : 588 - 600
  • [14] AN O(N LOG N) MANHATTAN PATH ALGORITHM
    LIPSKI, W
    INFORMATION PROCESSING LETTERS, 1984, 19 (02) : 99 - 102
  • [15] AN O(N LOG N LOG LOG N) PARALLEL MAXIMUM MATCHING ALGORITHM FOR BIPARTITE GRAPHS
    KIM, T
    CHWA, KY
    INFORMATION PROCESSING LETTERS, 1987, 24 (01) : 15 - 17
  • [16] Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time
    Lacki, Jakub
    Sankowski, Piotr
    ALGORITHMS - ESA 2011, 2011, 6942 : 155 - 166
  • [17] An O(n3/2 √log(n)) algorithm for sorting by reciprocal translocations
    Ozery-Flato, Michal
    Shamir, Ron
    COMBINATORIAL PATTERN MATCHING, PROCEEDINGS, 2006, 4009 : 258 - 269
  • [18] A Delaunay triangulation-based shortest path algorithm with O (n log n) time in the Euclidean plane
    Jan, Gene Eu
    Tsai, Wei Chun
    Sun, Chi-Chia
    Lin, Bor-Shing
    2012 IEEE/ASME INTERNATIONAL CONFERENCE ON ADVANCED INTELLIGENT MECHATRONICS (AIM), 2012, : 186 - 189
  • [19] Near-Shortest Path Planning on a Quadratic Surface With O(n log n) Time
    Sun, Chi-Chia
    Jan, Gene Eu
    Leu, Shao-Wei
    Yang, Kai-Chieh
    Chen, Yi-Chun
    IEEE SENSORS JOURNAL, 2015, 15 (11) : 6079 - 6080
  • [20] An O(log n log log n) space algorithm for undirected st-connectivity
    Trifonov, Vladimir
    SIAM JOURNAL ON COMPUTING, 2008, 38 (02) : 449 - 483
12345