Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman (1974):
The Design and Analysis of Computer Algorithms.
Addison-Wesley.
Ravindra K. Ahuja, Thomas L. Magnanti & James B. Orlin (1993):
Network flows: theory, algorithms, and applications.
Prentice Hall.
Noga Alon, Zvi Galil & Oded Margalit (1997):
On the Exponent of the All Pairs Shortest Path Problem.
Journal of Computer and System Sciences 54(2),
pp. 255–262,
doi:10.1006/jcss.1997.1388.
Announced at FOCS '91.
Roderick Bloem, Karin Greimel, Thomas A. Henzinger & Barbara Jobstmann (2009):
Synthesizing robust systems.
In: FMCAD,
pp. 85–92,
doi:10.1109/FMCAD.2009.5351139.
Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino & Bodo Manthey (2011):
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes.
In: ICALP,
pp. 147–158,
doi:10.1007/978-3-642-22006-7_13.
Peter Butkovic & Raymond A. Cuninghame-Green (1992):
An O(n^2) algorithm for the maximum cycle mean of an n n bivalent matrix..
Discrete Applied Mathematics 35(2),
pp. 157–162,
doi:10.1016/0166-218X(92)90039-D.
Timothy M. Chan (2010):
More Algorithms for All-Pairs Shortest Paths in Weighted Graphs.
SIAM Journal on Computing 39(5),
pp. 2075–2089,
doi:10.1137/08071990X.
Announced at STOC '07.
Ali Dasdan & Rajesh K. Gupta (1998):
Faster Maximum and Minimum Mean Cycle Algorithms for System-Performance Analysis.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 17(10),
pp. 889–899,
doi:10.1109/43.728912.
Manfred Droste & Ingmar Meinecke (2010):
Describing Average- and Longtime-Behavior by Weighted MSO Logics.
In: MFCS,
pp. 537–548,
doi:10.1007/978-3-642-15155-2_47.
Andrzej Ehrenfeucht & Jan Mycielski (1979):
Positional strategies for mean payoff games.
International Journal of Game Theory 8(2),
pp. 109–113,
doi:10.1007/BF01768705.
Michael L. Fredman (1976):
New Bounds on the Complexity of the Shortest Path Problem.
SIAM Journal on Computing 5(1),
pp. 83–89,
doi:10.1137/0205006.
Andrew V. Goldberg (1995):
Scaling Algorithms for the Shortest Paths Problem.
SIAM Journal on Computing 24(3),
pp. 494–504,
doi:10.1137/S0097539792231179.
V.A. Gurvich, A.V. Karzanov & L.G. Khachiyan (1988):
Cyclic games and an algorithm to find minimax cycle means in directed graphs.
USSR Computational Mathematics and Mathematical Physics 28(5),
pp. 85–91,
doi:10.1016/0041-5553(88)90012-2.
Thomas Dueholm Hansen & Uri Zwick (2010):
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles.
In: ISAAC,
pp. 415–426,
doi:10.1007/978-3-642-17517-6_37.
Mark Hartmann & James B. Orlin (1993):
Finding Minimum Cost to Time Ratio Cycles With Small Integral Transit Times.
Networks 23(6),
pp. 567–574,
doi:10.1002/net.3230230607.
Ronald A. Howard (1960):
Dynamic Programming and Markov Processes.
MIT Press.
Richard M. Karp (1978):
A characterization of the minimum cycle mean in a digraph.
Discrete Mathematics 23(3),
pp. 309–311,
doi:10.1016/0012-365X(78)90011-0.
Richard M. Karp & James B. Orlin (1981):
Parametric shortest path algorithms with an application to cyclic staffing.
Discrete Applied Mathematics 3(1),
pp. 37–45,
doi:10.1016/0166-218X(81)90026-3.
Eugène L. Lawler (1976):
Combinatorial optimization: Networks and Matroids.
Dover Publications.
S. Thomas McCormick (1993):
Approximate Binary Search Algorithms for Mean Cuts and Cycles.
Operations Research Letters 14(3),
pp. 129–132,
doi:10.1016/0167-6377(93)90022-9.
James B. Orlin & Ravindra K. Ahuja (1992):
New scaling algorithms for the assignment and minimum mean cycle problems.
Mathematical Programming 54(1-3),
pp. 41–56,
doi:10.1007/BF01586040.
Aaron Roth, Maria-Florina Balcan, Adam Kalai & Yishay Mansour (2010):
On the Equilibria of Alternating Move Games.
In: SODA,
pp. 805–816.
Available at http://dl.acm.org/citation.cfm?id=1873667.
Piotr Sankowski (2005):
Shortest Paths in Matrix Multiplication Time.
In: ESA,
pp. 770–778,
doi:10.1007/11561071_68.
Virginia Vassilevska Williams (2012):
Multiplying Matrices Faster Than Coppersmith-Winograd.
In: STOC,
pp. 887–898,
doi:10.1145/2213977.2214056.
Virginia Vassilevska Williams & Ryan Williams (2010):
Subcubic Equivalences between Path, Matrix and Triangle Problems.
In: FOCS,
pp. 645–654,
doi:10.1109/FOCS.2010.67.
Neal E. Young, Robert Endre Tarjan & James B. Orlin (1991):
Faster Parametric Shortest Path and Minimum-Balance algorithms.
Networks 21(2),
pp. 205–221,
doi:10.1002/net.3230210206.
Gideon Yuval (1976):
An algorithm for finding all shortest paths using N^2.81 infinite-precision multiplications.
Information Processing Letters 4(6),
pp. 155–156,
doi:10.1016/0020-0190(76)90085-5.
Eitan Zemel (1987):
A Linear Time Randomizing Algorithm for Searching Ranked Functions.
Algorithmica 2(1-4),
pp. 81–90,
doi:10.1007/BF01840350.
Uri Zwick (2002):
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication.
Journal of the ACM 49(3),
pp. 289–317,
doi:10.1145/567112.567114.
Announced at FOCS '98.
Uri Zwick & Mike Paterson (1996):
The complexity of mean payoff games on graphs.
Theoretical Computer Science 158(1-2),
pp. 343–359,
doi:10.1016/0304-3975(95)00188-3.
Announced at COCOON '95.
eptcs@eptcs.org