×

zbMATH — the first resource for mathematics

A survey of the all-pairs shortest paths problem and its variants in graphs. (English) Zbl 1362.68236
Summary: There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesely, Reading, 1974. ⇒19, 22 · Zbl 0326.68005
[2] A. Alon, Z. Galil, O. Margalit, go, J. Comput. Sys. Sci54, 2 (1997) 255-262. ⇒23, 25
[3] M. J. Atallah, D. Z. Chen, D. T. Lee, An optimal algorithm for shortest paths on weighted interval and circular arc graphs, with applications, Proc. European Sympos. on Algorithms, Lecture Notes in Computer Science726 (1993) 13-24. ⇒20
[4] A. T. Balaban, Applications of graph theory in chemistry, J. Chem. Inf. Comput, Sci.25, 3 (1985) 334-343. ⇒28
[5] V. Balachandhran, C. Pandu Rangan, All-pairs-shortest length on strongly chordal graphs, Discrete Appl. Math.69, 1-2 (1996) 169-182. ⇒20 · Zbl 0868.68084
[6] Y. A. Ban, S. Bereg, N. H. Mustafa, A conjecture on Wiener indices in combinatorial chemistry, Algorithmica40, 2 (2004) 99-117. ⇒17, 30 · Zbl 1088.05503
[7] G. E. Blelloch, V. Vassilevska, R. Williams, A new combinatorial approach for sparse graph problems, Proc. International Colloquium on Automata, Languages and Programming35 (2008) 108-120. ⇒25 · Zbl 1152.68426
[8] A. Brandstädt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, SIAM Monogr. Disc. Math. Appl. 1999. ⇒27
[9] R. M. Casablanca, Average distance in the strong product of graphs, Util. Math.94 (2014) 31-48. ⇒29 · Zbl 1300.05082
[10] T. M. Chan, All-pairs shortest paths with real weights in O(n3=logn) time, Proc. 9th Workshop Algorithms Data Struct., Lecture Notes in Computer Science3608 (2005) 318-324. Also available in Algorithmica50, 2 (2008) 236-243. ⇒22 · Zbl 1151.68043
[11] T. M. Chan, All-pairs shortest paths for unweighted undirected graphs in o(mn) time, Proc. ACM-SIAM Sympos. Discrete Algorithms17 (2006) 514-523. ⇒25 · Zbl 1192.05154
[12] T. M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, In Proc. 39th ACM Symposium on Theory of Computing (STOC) (2007) 590-598. ⇒22 · Zbl 1231.05245
[13] V. Chepoi, S. Klavžar, The Wiener index and the Szeged index of benzenoid systems in linear time, J. Chem. Inf. Comput. Sci.37, 4 (1997) 752-755. ⇒29
[14] V. Chepoi, S. Klavžar, Distances in benzenoid systems: further developments, Discrete Math.192, 1-3 (1998) 27-39. ⇒29
[15] F. R. K. Chung, The average distance and the independence number, J. Graph Theory12, 2 (1988) 229-235. ⇒29, 32 · Zbl 0644.05029
[16] E. Cohen, Using selective path-doubling for parallel shortest-path computations, J. Algorithms22, 1 (1997) 30-56. ⇒20 · Zbl 0872.68061
[17] E. Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, J. ACM47, 1 (2000) 132-166. ⇒20 · Zbl 1094.68700
[18] D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. of Symb. Comput.9, 3 (1990) 251-280. ⇒23 · Zbl 0702.65046
[19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (3rd edition), The MIT Press, 2009. ⇒16, 17, 21, 24, 27 · Zbl 1187.68679
[20] E. Dahlhaus, Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes, Proc. of the International Workshop Graph-Theoretic Concepts in Comput. Sci., Lecture Notes in Computer Science657 (1992) 60-69. ⇒20 · Zbl 0789.68062
[21] E. Dahlhaus, P. Dankelmann, W. Goddard, H. C. Swart, MAD trees and distance-hereditary graphs, Discrete Appl. Math.131, 1 (2003) 151-167. ⇒33, 34 · Zbl 1022.05023
[22] E. Dahlhaus, P. Dankelmann, R. Ravi, A linear-time algorithm to compute a MAD tree of an interval graph, Inf. Process. Lett.89, 5 (2004) 255-259. ⇒33 · Zbl 1183.68415
[23] P. Dankelmann, Computing the average distance of an interval graph, Inform. Process. Lett.48, 6 (1993) 311-314. ⇒29, 31, 32 · Zbl 0813.68141
[24] P. Dankelmann, Average distance and independence number, Discrete Appl. Math.51, 1-2 (1994) 75-83. ⇒29, 30 · Zbl 0803.05020
[25] P. Dankelmann, Average distance and domination number, Discrete Appl. Math.80, 1 (1997) 21-35. ⇒29 · Zbl 0888.05024
[26] P. Dankelmann, Average distance in weighted graphs, Discrete Math.312, 1 (2012) 12-20. ⇒29 · Zbl 1238.05071
[27] E. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik1, 1 (1959) 269-271. ⇒21 · Zbl 0092.16002
[28] C. Demetrescu, G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n2) barrier, Proc. IEEE Sympos. on Found. Comput. Sci.41 (2000) 381-389. ⇒20
[29] J. K. Doyle, J. E. Graver, Mean distance in a graph, Discrete Math.17, 2 (1977) 147-154. ⇒29 · Zbl 0361.05045
[30] W. Dobosiewicz, A more efficient algorithm for the min-plus multiplication, Int. J. Comput. Math.32, 1-2 (1990) 49-60. ⇒22 · Zbl 0825.68412
[31] A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math.66, 3 (2001) 211-249. ⇒17, 28, 29, 30, 34 · Zbl 0982.05044
[32] A. A. Dobrynin, I. Gutman, S. Klavžar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math.72, 3 (2002) 247-294. ⇒30 · Zbl 0993.05059
[33] F. F. Dragan. Estimating all pairs shortest paths in restricted graph families: a unified approach. J. of Algorithms57, 1 (2005) 1-21. ⇒17, 26, 27 · Zbl 1105.68087
[34] R. C. Entringer, D. E. Jackson, D. A. Synder, Distance in graphs, Czech. Math. J.26, 2 (1976) 283-296. ⇒30 · Zbl 0329.05112
[35] R. C. Entringer, Distance in graphs: trees, J. Combin. Math. Combin. Comput.24 (1997) 65-84. ⇒33 · Zbl 0880.05029
[36] R. C. Entringer, D. J. Kleitman, L. A. Sžekely, A note on spanning trees with minimum average distance, Bull. Inst. Combin. Appl.17 (1996) 71-78. ⇒33 · Zbl 0847.05051
[37] A. X. Falcao, J. K. Udupa, S. Samarasekera, S. Sharma, B. E. Hirsch, R. A. Lotufo, User-steered image segmentation paradigms: Live wire and live lane, Graphical Models and Image Process.60, 4 (1998) 233-260. ⇒16
[38] T. Feder, R. Motwani, Clique patritions, graph compression and speeding-up algorithms, J. Comput. Sys. Sci. 51, 2 (1995) 261-272. ⇒25 · Zbl 0831.68073
[39] A. M. Fitch, and M. B. Jones, Shortest path analysis using partial correlations for classifying gene functions from gene expression data, Bioinformatics25 (2009) 42-47. ⇒17
[40] M. Fredman, R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM34, 3 (1987) 596-615. ⇒21, 24 · Zbl 1412.68048
[41] M. L. Fredman, New bounds on the complexity of the shortest path problem, SIAM J. Comput. 5, 1 (1976) 49-60. ⇒22 · Zbl 0326.68027
[42] Z. Galil, O. Margalit, All pairs shortest distances for graphs with small integer length edges, Inform. Comput.134, 2 (1997) 103-139. ⇒23, 24, 25 · Zbl 0879.68081
[43] T. Hagerup, Improved shortest paths on the word RAM, Proc. International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science1853 (2000) 61-72. ⇒24, 27 · Zbl 0973.68535
[44] K. Han, C. N. Sekharan, R. Sridhar, Unified all-pairs shortest path algorithms in the chordal hierarchy, Discrete Appl. Math.77, 1 (1997) 59-71. ⇒20, 26 · Zbl 0879.05065
[45] Y. Han, M. Thorup, Integer sorting in \({\rm{O}}\left( {{\rm{n}}\sqrt{\log \;\log \;{\rm{n}}} } \right)\) expected time and linear space, Symp. on Found. of Comput. Sci.43 (2002) 135-144. ⇒24
[46] Y. Han, Improved algorithm for all pairs shortest paths, Inform. Process. Lett.91, 5 (2004) 245-250. ⇒22 · Zbl 1178.68658
[47] Y. Han, An O(n3(loglogn=logn)5=4) time algorithm for all pairs shortest paths, Proc. European Sympos. Algorithms, Lecture Notes in Computer Science4168 (2006) 411-417. ⇒22 · Zbl 1131.68464
[48] Y. Han, T. Takaoka, An O(n3 log log n= log2n) time algorithm for all pairs shortest paths, Proc. 13th SWAT, Lecture Notes in Computer Science7357 (2012) 131-141. ⇒23 · Zbl 1357.05145
[49] M. R. Henzinger, P. Klein, S. Rao, S. Subramanian, Faster shortest-path algorithms for planar graphs, J. Comput. System Sci.55, 1 (1997) 3-23. ⇒26 · Zbl 0880.68099
[50] B. Jana, S. Mondal, Computation of a minimum average distance tree on permutation graphs, Annals of Pure and Appl. Math.2, 1 (2012) 74-85. ⇒34
[51] D. Johnson, Efficient algorithms for shortest paths in sparse graphs, J. ACM24, 1 (1977) 1-13. ⇒21, 23, 24 · Zbl 0343.68028
[52] D. S. Johnson, J. K. Lenstra, A. H. G. Rinnooy-Kan, The complexity of the network design problem, Networks8, 4 (1978) 279-285. ⇒33 · Zbl 0395.94048
[53] V. King, Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, Proc. IEEE Sympos. on Found. of Comput. Sci.40 (1999) 81-89. ⇒20
[54] S. Klavžar, and I. Gutman, Wiener number of vertex-weighted graphs and a chemical applications, Discrete Appl. Math.80, 1 (1997) 73-81. ⇒18 · Zbl 0889.05046
[55] S. Klavžar, P. Manuel, M. J. Nadjafi-Arani, R. Sundara Rajan, C. Grigorious, S. Stephen, Average distance in interconnection networks via reduction theorems for vertex-weighted graphs, To appear ⇒28, 29, 31, 32, 33
[56] F. Le Gall, Faster algorithms for rectangular matrix multiplication, Proc. 53rd FOCS (2012) 514-523. ⇒23, 25, 27 · Zbl 1422.68079
[57] P. Mirchandani, A simple O(n2) algorithm for the all-pairs shortest path problem on an interval graph, Networks27, 3 (1996) 215-217. ⇒20 · Zbl 0851.90127
[58] B. Mohar, T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem.2 (1988) 267-277. ⇒29
[59] S. Mondal, M. Pal, T. K. Pal, An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs, Int. J. Comp. Eng. Sci.3, 2 (2002) 103-116. ⇒26
[60] S. Mondal, An efficient algorithm for computation of a minimum average distance tree on trapezoid graphs, J. Scientific Research and Reports2, 2 (2013) 598-611. ⇒34
[61] E. N. Mortensen, W. A. Barrett, Interactive segmentation with intelligent scissors, Graphical Models and Image Process.60, 5 (1998) 349-384. ⇒16 · Zbl 0914.68210
[62] S. Mukwembi, Average distance, independence number, and spanning trees, J. Graph Theory76, 3 (2014) 194-199. ⇒29 · Zbl 1296.05049
[63] W. Peng, X. Hu, F. Zhao, J. Su, A fast algorithm to find all-pairs shortest paths in complex networks, Procedia Comp. Sci.9 (2012) 557-566. ⇒16
[64] S. Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoret. Comput. Sci. 312, 1 (2004) 47-74. ⇒21, 24 · Zbl 1071.68084
[65] S. Pettie, V. Ramachandran, A shortest path algorithm for real-weighted undirected graphs, SIAM J. Comput.34, 6 (2005) 1398-1431. ⇒24 · Zbl 1078.05080
[66] S. Peyer, D. Rautenbach, J. Vygen, A generalization of Dijkstras shortest path algorithm with applications to VLSI routing, J. Discrete Algorithms7, 4 (2009) 377-390. ⇒16 · Zbl 1176.90612
[67] M. Randic, Chemical graph theory-facts and fiction, Ind. J. Chem.42A (2003) 1207-1218. ⇒28
[68] R. Ravi, M. V. Marathe, C. Pandu Rangan, An optimal algorithm to solve the all-pair shortest path problem on interval graphs, Networks22, 1 (1992) 21-35. ⇒20 · Zbl 0761.90096
[69] A. Saha, M. Pal, T. K. Pal, An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs, J. Appl. Math. and Computing17 1 (2005) 1-23. ⇒27 · Zbl 1102.68137
[70] J. P. Schmidt, All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings, SIAM J. Comput.27, 4 (1998) 972-992. ⇒16 · Zbl 0907.68076
[71] R. Seidel, On the all-pairs shortest path problem in unweighted undirected graphs, J. Comput. Sys. Sci.51, 3 (1995) 400-403. ⇒23, 24, 25 · Zbl 1295.05240
[72] T. Shinn, T. Takaoka, Combining all pairs shortest paths and all pairs bottleneck paths problems, Lecture Notes in Computer Science8392 (2014) 226-237. ⇒23 · Zbl 1405.68254
[73] A. Shoshan, U. Zwick, All pairs shortest paths in undirected graphs with integer weights, Proc. IEEE Sympos. on Found. of Comput. Sci.40 (1999) 605-614. ⇒23, 27
[74] C. Sommer, Approximate shortest path and distance queries in networks, PhD thesis, The University of Tokyo, 2010. ⇒20
[75] R. Sridhar, D. Joshi, N. Chandrasekharan, Efficient algorithms for shortest distance queries on interval, directed path and circular arc graphs, Proc. Int’l. Conf. on Comput. and Inf.5 (1993) 31-35. ⇒20
[76] V. Strassen, Gaussian elimination is not optimal, Numer. Math.13, 4 (1969) 354-356. ⇒23 · Zbl 0185.40101
[77] T. Takaoka, A new upper bound on the complexity of the all pairs shortest path problem, Inform. Process. Lett.43, 4 (1992) 195-199. ⇒22 · Zbl 0763.68044
[78] T. Takaoka, A faster algorithm for the all-pairs shortest path problem and its application, Proc. 10th Int. Conf. Comput. Comb., Lecture Notes in Computer Science3106 (2004) 278-289. ⇒22 · Zbl 1091.68082
[79] M. Tchuente, P. M. Yonta, J. Nlong II, Y. Denneulin, On the minimum average distance spanning tree of the hypercube, Acta Appl. Math.102, 2-3 (2008) 219-236. ⇒34 · Zbl 1155.05056
[80] M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time, J. ACM46, 3 (1999) 362-394. ⇒24 · Zbl 1065.68597
[81] M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, J. Comp. Sys. Sci.69, 3 (2004) 330-353. ⇒24 · Zbl 1084.68030
[82] N. Trinajstic, Chemical Graph Theory, CRC Press, Boca raton, FL, 1992. ⇒28
[83] K. R. Udaya Kumar Reddy, Computing average distance on strongly chordal graphs, National J. Tech.8, 1 (2012) 26-35. ⇒31, 32
[84] V. Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, Proc. 44th ACM Symposium on Theory of Computing (to appear, 2012). ⇒23 · Zbl 1286.65056
[85] K. V. Iyer, K. R. Udaya Kumar Reddy, Weiner index of binomial trees and Fibonacci trees, Int. J. Math. Engg. with Comp.1 (2010) 27-34. Also available at . ⇒31, 32
[86] B. Y. Wu, G. Lancia, V. Bafna, K. M. Chao, R. Ravi, C. Y. Tang, A polynomial-time approximation scheme for minimum routing cost spanning trees, SIAM J. Comput.29, 3 (2000) 761-778. ⇒33 · Zbl 0941.68159
[87] L. Xu, X. Guo, Catacondensed hexagonal systems with large Wiener numbers, MATCH Commun. Math. Comput. Chem.55, 1 (2006) 137-158. ⇒28 · Zbl 1088.05071
[88] S. J. Xu, R. Gysel, D. Gusfield, Minimum average distance clique trees, SIAM J. Discrete Math.29, 3 (2015) 1706-1734. ⇒28, 29 · Zbl 1337.68213
[89] B. Zmazek, J. Žerovnik, Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time, Croat. Chem. Acta.76, 2 (2003) 137-143. ⇒32
[90] U. Zwick, Exact and approximate distances in graphs: a survey, Proc. European Symp. on Algorithms9 (2001) 33-48. ⇒18, 27 · Zbl 1006.68543
[91] U. Zwick, All-pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM49, 3 (2002) 289-317. ⇒22, 23, 25 · Zbl 1326.05157
[92] U. Zwick, A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths, Proc. Int. Sympos. Algorithms and Computation, Lecture Notes in Computer Science3341 (2004) 921-932. ⇒22 · Zbl 1116.68564
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.