Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms

被引：44

作者：

Demetrescu, Camil ^{[1
]}

Italiano, Giuseppe F. ^{[2
]}

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, Rome, Italy

[2] Univ Roma Tor Vergata, Dipartimento Informat Sistemi & Prod, Rome, Italy

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2006年 / 2卷 / 04期

关键词：

Algorithms; Dynamic graph algorithms; shortest paths; experimental algorithmics;

D O I：

10.1145/1198513.1198519

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [1999] and of Demetrescu and Italiano [2006], and compare them to the dynamic algorithm of Ramalingam and Reps and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.

引用

页数：24

共 30 条

[1]

ALBERTS D, 1997, ACM J EXP ALGORITHMI, V2, P5

[2]

Amato G, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P314

[3]

BURIOL LS, 2003, TD5RJ8B AT T LABS RE

[4]

Cattaneo G, 2002, LECT NOTES COMPUT SC, V2409, P111

[5] Shortest paths algorithms: Theory and experimental evaluation [J].

Cherkassky, BV ;

Goldberg, AV ;

Radzik, T .

MATHEMATICAL PROGRAMMING, 1996, 73 (02) :129-174

[6] A new approach to dynamic all pairs shortest paths [J].

Demetrescu, C ;

Italiano, GF .

JOURNAL OF THE ACM, 2004, 51 (06) :968-992

[7]

DEMETRESCU C, 2003, P 35 ANN ACM S THEOR, P159

[8]

DEMETRESCU C, 2000, P 4 WORKSH ALG ENG W

[9] Fully dynamic all pairs shortest paths with real edge weights [J].

Demetrescu, Camil ;

Italiano, Giuseppe F. .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (05) :813-837

[10]

Dijkstra E, 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

← 1 2 3 →