A survey of the all-pairs shortest paths problem and its variants in graphs

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesely, Reading, 1974. ⇒19, 22Search in Google Scholar

[2] A. Alon, Z. Galil, O. Margalit, go, J. Comput. Sys. Sci54, 2 (1997) 255–262. ⇒23, 2510.1006/jcss.1997.1388Search in Google Scholar

[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. ⇒2010.1007/3-540-57273-2_40Search in Google Scholar

[4] A. T. Balaban, Applications of graph theory in chemistry, J. Chem. Inf. Comput, Sci.25, 3 (1985) 334–343. ⇒2810.1021/ci00047a033Search in Google Scholar

[5] V. Balachandhran, C. Pandu Rangan, All-pairs-shortest length on strongly chordal graphs, Discrete Appl. Math.69, 1–2 (1996) 169–182. ⇒2010.1016/0166-218X(95)00088-9Search in Google Scholar

[6] Y. A. Ban, S. Bereg, N. H. Mustafa, A conjecture on Wiener indices in combinatorial chemistry, Algorithmica40, 2 (2004) 99–117. ⇒17, 3010.1007/s00453-004-1097-ySearch in Google Scholar

[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. ⇒2510.1007/978-3-540-70575-8_10Search in Google Scholar

[8] A. Brandstädt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, SIAM Monogr. Disc. Math. Appl. 1999. ⇒2710.1137/1.9780898719796Search in Google Scholar

[9] R. M. Casablanca, Average distance in the strong product of graphs, Util. Math.94 (2014) 31–48. ⇒29Search in Google Scholar

[10] T. M. Chan, All-pairs shortest paths with real weights in O(n³=logn) time, Proc. 9th Workshop Algorithms Data Struct., Lecture Notes in Computer Science3608 (2005) 318–324. Also available in Algorithmica50, 2 (2008) 236–243. ⇒2210.1007/11534273_28Search in Google Scholar

[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. ⇒2510.1145/1109557.1109614Search in Google Scholar

[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. ⇒2210.1145/1250790.1250877Search in Google Scholar

[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. ⇒2910.1021/ci9700079Search in Google Scholar

[14] V. Chepoi, S. Klavžar, Distances in benzenoid systems: further developments, Discrete Math.192, 1–3 (1998) 27–39. ⇒2910.1016/S0012-365X(98)00064-8Search in Google Scholar

[15] F. R. K. Chung, The average distance and the independence number, J. Graph Theory12, 2 (1988) 229–235. ⇒29, 3210.1002/jgt.3190120213Search in Google Scholar

[16] E. Cohen, Using selective path-doubling for parallel shortest-path computations, J. Algorithms22, 1 (1997) 30–56. ⇒2010.1006/jagm.1996.0813Search in Google Scholar

[17] E. Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, J. ACM47, 1 (2000) 132–166. ⇒2010.1145/331605.331610Search in Google Scholar

[18] D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. of Symb. Comput.9, 3 (1990) 251–280. ⇒2310.1016/S0747-7171(08)80013-2Search in Google Scholar

[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, 27Search in Google Scholar

[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. ⇒2010.1007/3-540-56402-0_36Search in Google Scholar

[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, 3410.1016/S0166-218X(02)00422-5Search in Google Scholar

[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. ⇒3310.1016/j.ipl.2003.11.009Search in Google Scholar

[23] P. Dankelmann, Computing the average distance of an interval graph, Inform. Process. Lett.48, 6 (1993) 311–314. ⇒29, 31, 3210.1016/0020-0190(93)90174-8Search in Google Scholar

[24] P. Dankelmann, Average distance and independence number, Discrete Appl. Math.51, 1–2 (1994) 75–83. ⇒29, 3010.1016/0166-218X(94)90095-7Search in Google Scholar

[25] P. Dankelmann, Average distance and domination number, Discrete Appl. Math.80, 1 (1997) 21–35. ⇒2910.1016/S0166-218X(97)00067-XSearch in Google Scholar

[26] P. Dankelmann, Average distance in weighted graphs, Discrete Math.312, 1 (2012) 12–20. ⇒2910.1016/j.disc.2011.02.010Search in Google Scholar

[27] E. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik1, 1 (1959) 269–271. ⇒2110.1007/BF01386390Search in Google Scholar

[28] C. Demetrescu, G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n²) barrier, Proc. IEEE Sympos. on Found. Comput. Sci.41 (2000) 381–389. ⇒20Search in Google Scholar

[29] J. K. Doyle, J. E. Graver, Mean distance in a graph, Discrete Math.17, 2 (1977) 147–154. ⇒2910.1016/0012-365X(77)90144-3Search in Google Scholar

[30] W. Dobosiewicz, A more efficient algorithm for the min-plus multiplication, Int. J. Comput. Math.32, 1–2 (1990) 49–60. ⇒2210.1080/00207169008803814Search in Google Scholar

[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, 3410.1023/A:1010767517079Search in Google Scholar

[32] A. A. Dobrynin, I. Gutman, S. Klavžar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math.72, 3 (2002) 247–294. ⇒3010.1023/A:1016290123303Search in Google Scholar

[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, 2710.1016/j.jalgor.2004.09.002Search in Google Scholar

[34] R. C. Entringer, D. E. Jackson, D. A. Synder, Distance in graphs, Czech. Math. J.26, 2 (1976) 283–296. ⇒3010.21136/CMJ.1976.101401Search in Google Scholar

[35] R. C. Entringer, Distance in graphs: trees, J. Combin. Math. Combin. Comput.24 (1997) 65–84. ⇒33Search in Google Scholar

[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. ⇒33Search in Google Scholar

[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. ⇒1610.1006/gmip.1998.0475Search in Google Scholar

[38] T. Feder, R. Motwani, Clique patritions, graph compression and speeding-up algorithms, J. Comput. Sys. Sci. 51, 2 (1995) 261–272. ⇒2510.1006/jcss.1995.1065Search in Google Scholar

[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. ⇒1710.1093/bioinformatics/btn574Search in Google Scholar

[40] M. Fredman, R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM34, 3 (1987) 596–615. ⇒21, 2410.1145/28869.28874Search in Google Scholar

[41] M. L. Fredman, New bounds on the complexity of the shortest path problem, SIAM J. Comput. 5, 1 (1976) 49–60. ⇒2210.1137/0205006Search in Google Scholar

[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, 2510.1006/inco.1997.2620Search in Google Scholar

[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, 2710.1007/3-540-45022-X_7Search in Google Scholar

[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, 2610.1016/S0166-218X(96)00103-5Search in Google Scholar

[45] Y. Han, M. Thorup, Integer sorting in O(nlog log n)${\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. ⇒24Search in Google Scholar

[46] Y. Han, Improved algorithm for all pairs shortest paths, Inform. Process. Lett.91, 5 (2004) 245–250. ⇒2210.1016/j.ipl.2004.05.006Search in Google Scholar

[47] Y. Han, An O(n³(loglogn=logn)5=4) time algorithm for all pairs shortest paths, Proc. European Sympos. Algorithms, Lecture Notes in Computer Science4168 (2006) 411–417. ⇒2210.1007/11841036_38Search in Google Scholar

[48] Y. Han, T. Takaoka, An O(n³ log log n= log²n) time algorithm for all pairs shortest paths, Proc. 13th SWAT, Lecture Notes in Computer Science7357 (2012) 131–141. ⇒2310.1007/978-3-642-31155-0_12Search in Google Scholar

[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. ⇒2610.1006/jcss.1997.1493Search in Google Scholar

[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. ⇒34Search in Google Scholar

[51] D. Johnson, Efficient algorithms for shortest paths in sparse graphs, J. ACM24, 1 (1977) 1–13. ⇒21, 23, 2410.1145/321992.321993Search in Google Scholar

[52] D. S. Johnson, J. K. Lenstra, A. H. G. Rinnooy-Kan, The complexity of the network design problem, Networks8, 4 (1978) 279–285. ⇒3310.1002/net.3230080402Search in Google Scholar

[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. ⇒20Search in Google Scholar

[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. ⇒1810.1016/S0166-218X(97)00070-XSearch in Google Scholar

[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, 33Search in Google Scholar

[56] F. Le Gall, Faster algorithms for rectangular matrix multiplication, Proc. 53rd FOCS (2012) 514–523. ⇒23, 25, 2710.1109/FOCS.2012.80Search in Google Scholar

[57] P. Mirchandani, A simple O(n²) algorithm for the all-pairs shortest path problem on an interval graph, Networks27, 3 (1996) 215–217. ⇒2010.1002/(SICI)1097-0037(199605)27:3<215::AID-NET6>3.0.CO;2-LSearch in Google Scholar

[58] B. Mohar, T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem.2 (1988) 267–277. ⇒2910.1007/BF01167206Search in Google Scholar

[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. ⇒2610.1142/S1465876302000575Search in Google Scholar

[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. ⇒3410.9734/JSRR/2013/4661Search in Google Scholar

[61] E. N. Mortensen, W. A. Barrett, Interactive segmentation with intelligent scissors, Graphical Models and Image Process.60, 5 (1998) 349–384. ⇒1610.1006/gmip.1998.0480Search in Google Scholar

[62] S. Mukwembi, Average distance, independence number, and spanning trees, J. Graph Theory76, 3 (2014) 194–199. ⇒2910.1002/jgt.21758Search in Google Scholar

[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. ⇒1610.1016/j.procs.2012.04.060Search in Google Scholar

[64] S. Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoret. Comput. Sci. 312, 1 (2004) 47–74. ⇒21, 2410.1016/S0304-3975(03)00402-XSearch in Google Scholar

[65] S. Pettie, V. Ramachandran, A shortest path algorithm for real-weighted undirected graphs, SIAM J. Comput.34, 6 (2005) 1398–1431. ⇒2410.1137/S0097539702419650Search in Google Scholar

[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. ⇒1610.1016/j.jda.2007.08.003Search in Google Scholar

[67] M. Randic, Chemical graph theory-facts and fiction, Ind. J. Chem.42A (2003) 1207–1218. ⇒28Search in Google Scholar

[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. ⇒2010.1002/net.3230220103Search in Google Scholar

[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. ⇒2710.1007/BF02936037Search in Google Scholar

[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. ⇒1610.1137/S0097539795288489Search in Google Scholar

[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, 2510.1006/jcss.1995.1078Search in Google Scholar

[72] T. Shinn, T. Takaoka, Combining all pairs shortest paths and all pairs bottleneck paths problems, Lecture Notes in Computer Science8392 (2014) 226–237. ⇒2310.1007/978-3-642-54423-1_20Search in Google Scholar

[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, 27Search in Google Scholar

[74] C. Sommer, Approximate shortest path and distance queries in networks, PhD thesis, The University of Tokyo, 2010. ⇒20Search in Google Scholar

[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. ⇒20Search in Google Scholar

[76] V. Strassen, Gaussian elimination is not optimal, Numer. Math.13, 4 (1969) 354–356. ⇒2310.1007/BF02165411Search in Google Scholar

[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. ⇒2210.1016/0020-0190(92)90200-FSearch in Google Scholar

[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. ⇒2210.1007/978-3-540-27798-9_31Search in Google Scholar

[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. ⇒3410.1007/s10440-008-9215-5Search in Google Scholar

[80] M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time, J. ACM46, 3 (1999) 362–394. ⇒2410.1145/316542.316548Search in Google Scholar

[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. ⇒2410.1016/j.jcss.2004.04.003Search in Google Scholar

[82] N. Trinajstic, Chemical Graph Theory, CRC Press, Boca raton, FL, 1992. ⇒28Search in Google Scholar

[83] K. R. Udaya Kumar Reddy, Computing average distance on strongly chordal graphs, National J. Tech.8, 1 (2012) 26–35. ⇒31, 32Search in Google Scholar

[84] V. Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, Proc. 44th ACM Symposium on Theory of Computing (to appear, 2012). ⇒2310.1145/2213977.2214056Search in Google Scholar

[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 http://arxiv.org/abs/0910.4432. ⇒31, 32Search in Google Scholar

[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. ⇒3310.1137/S009753979732253XSearch in Google Scholar

[87] L. Xu, X. Guo, Catacondensed hexagonal systems with large Wiener numbers, MATCH Commun. Math. Comput. Chem.55, 1 (2006) 137–158. ⇒28Search in Google Scholar

[88] S. J. Xu, R. Gysel, D. Gusfield, Minimum average distance clique trees, SIAM J. Discrete Math.29, 3 (2015) 1706–1734. ⇒28, 2910.1137/15M1021052Search in Google Scholar

[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. ⇒32Search in Google Scholar

[90] U. Zwick, Exact and approximate distances in graphs: a survey, Proc. European Symp. on Algorithms9 (2001) 33–48. ⇒18, 2710.1007/3-540-44676-1_3Search in Google Scholar

[91] U. Zwick, All-pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM49, 3 (2002) 289-317. ⇒22, 23, 2510.1145/567112.567114Search in Google Scholar

[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. ⇒2210.1007/978-3-540-30551-4_78Search in Google Scholar