All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time

by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster

Theory of Computing, Volume 5(9), pp. 173-189, 2009

Bibliography with links to cited articles

[1]   A. V. Aho, J. E. Hopcroft, and J. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Boston, MA, 1974.

[2]   T. M. Chan: More algorithms for all-pairs shortest paths in weighted graphs. In Proc. 39th STOC, pp. 590–598. ACM Press, 2007. [STOC:1250790.1250877].

[3]   T. M. Chan: All-pairs shortest paths with real weights in O(n3log n) time. Algorithmica, 50(2):236–243, 2008. [Algorithmica:px2741688g4p4l18].

[4]   D. Coppersmith: Rectangular matrix multiplication revisited. J. Complexity, 13(1):42–49, 1997. [doi:10.1006/jcom.1997.0438].

[5]   D. Coppersmith and S. Winograd: Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9(3):251–280, 1990. [doi:10.1016/S0747-7171(08)80013-2].

[6]   R. Duan and S. Pettie: Fast algorithms for (max,min)-matrix multiplication and bottleneck shortest paths. In Proc. 19th SODA, pp. 384–391. ACM Press, 2009. [SODA:1496770.1496813].

[7]   D. Dubois and H. Prade: Fuzzy Sets and Systems: Theory and Applications. Academic Press, 1980.

[8]   M. J. Fischer and A. R. Meyer: Boolean matrix multiplication and transitive closure. In Proc. 12th FOCS, pp. 129–131. IEEE Comp. Soc. Press, 1971.

[9]   M. L. Fredman and R. E. Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596–615, 1987. [JACM:28869.28874].

[10]   M. E. Furman: Applications of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Dokl. Akad. Nauk SSSR (in Russian), 194:524, 1970.

[11]   M. E. Furman: Applications of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Soviet Math. Dokl. (in English), 11(5):1252, 1970.

[12]   Z. Galil and O. Margalit: All pairs shortest paths for graphs with small integer length edges. J. Comput. System Sci., 54:243–254, 1997. [JCSS:10.1006/jcss.1997.1385].

[13]   T. C. Hu: The maximum capacity route problem. Oper. Res., 9(6):898–900, 1961.

[14]   X. Huang and V. Y. Pan: Fast rectangular matrix multiplication and applications. J. Complexity, 14(2):257–299, 1998. [doi:10.1006/jcom.1998.0476].

[15]   D. S. Johnson: Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256–278, 1974. [JCSS:10.1016/S0022-0000(74)80044-9].

[16]   D. Karger, D. Koller, and S. Phillips: Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput., 22(6):1199–1217, 1993. [SICOMP:10.1137/0222071].

[17]   M. Kowaluk and A. Lingas: LCA queries in directed acyclic graphs. In Proc. 32nd Int. Colloq. Autom Lang. Program. (ICALP), volume 3580, pp. 241–248. Springer-Verlag, 2005. [ICALP:252dpgap58fdhchf].

[18]   L. Lovász: On the ratio of optimal integral and fractional covers. Discrete Math., 13:383–390, 1975. [doi:10.1016/0012-365X(75)90058-8].

[19]   J. Matoušek: Computing dominances in En. Inform. Process. Lett., 38(5):277–278, 1991. [IPL:10.1016/0020-0190(91)90071-O].

[20]   J. I. Munro: Efficient determination of the transitive closure of a directed graph. Inform. Process. Lett., 1(2):56–58, 1971. [IPL:10.1016/0020-0190(71)90006-8].

[21]   M. Pollack: The maximum capacity through a network. Oper. Res., 8(5):733–736, 1960.

[22]   R. Seidel: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. System Sci., 51:400–403, 1995. [JCSS:10.1006/jcss.1995.1078].

[23]   A. Shapira, R. Yuster, and U. Zwick: All-pairs bottleneck paths in vertex weighted graphs. In Proc. 17th SODA, pp. 978–985. ACM Press, 2007. [SODA:1283383.1283488].

[24]   A. Shoshan and U. Zwick: All pairs shortest paths in undirected graphs with integer weights. In Proc. 40th FOCS, pp. 605–614. IEEE Comp. Soc. Press, 1999. [FOCS:10.1109/SFFCS.1999.814635].

[25]   S. K. Stein: Two combinatorial covering theorems. J. Combin. Theory Ser. A, 16:391–397, 1974. [JCombThA:10.1016/0097-3165(74)90062-4].

[26]   C. R. Subramanian: A generalization of Janson inequalities and its application to finding shortest paths. In Proc. 10th SODA, pp. 795–804. ACM Press, 1999. [SODA:314500.314917].

[27]   V. Vassilevska: Nondecreasing paths in weighted graphs, or: How to optimally read a train schedule. In Proc. 18th SODA, pp. 465–472. ACM Press, 2008. [SODA:1347082.1347133].

[28]   V. Vassilevska and R. Williams: Finding a maximum weight triangle in n3-δ time, with applications. In Proc. 38th STOC, pp. 225–231. ACM Press, 2006. [STOC:1132516.1132550].

[29]   V. Vassilevska, R. Williams, and R. Yuster: All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proc. 39th STOC, pp. 585–589. ACM Press, 2007. [STOC:1250790.1250876].

[30]   U. Zwick: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289–317, 2002. [JACM:567112.567114].