Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman (1974):
The Design and Analysis of Computer Algorithms.
Addison-Wesley.
Noga Alon, Zvi Galil & Oded Margalit (1997):
On the Exponent of the All Pairs Shortest Path Problem.
J. Comput. Syst. Sci. 54(2),
pp. 255–262,
doi:10.1006/jcss.1997.1388.
Aaron Bernstein, Danupon Nanongkai & Christian Wulff-Nilsen (2022):
Negative-Weight Single-Source Shortest Paths in Near-linear Time.
In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022.
IEEE,
pp. 600–611,
doi:10.1109/FOCS54457.2022.00063.
Henrik Björklund & Sergei G. Vorobyov (2007):
A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games.
Discrete Applied Mathematics 155(2),
pp. 210–229,
doi:10.1016/j.dam.2006.04.029.
Announced at MFCS 2004.
Roderick Bloem, Krishnendu Chatterjee, Thomas A. Henzinger & Barbara Jobstmann (2009):
Better Quality in Synthesis through Quantitative Objectives.
In: Proc. of the 21st International Conference on Computer Aided Verification (CAV 2009),
Lecture Notes in Computer Science 5643.
Springer,
pp. 140–156,
doi:10.1007/978-3-642-02658-4_14.
ArXiv:0904.2638.
Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey & Jirí Srba (2008):
Infinite Runs in Weighted Timed Automata with Energy Constraints.
In: Franck Cassez & Claude Jard: Proc. of the 6th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2008),
Lecture Notes in Computer Science 5215.
Springer,
pp. 33–47,
doi:10.1007/978-3-540-85778-5_4.
Phillip G. Bradford (2017):
Efficient exact paths for dyck and semi-dyck labeled path reachability (extended abstract).
In: Proc. of the 8th IEEE Annual Conference on Ubiquitous Computing, Electronics and Mobile Communication (UEMCON 2017).
IEEE,
pp. 247–253,
doi:10.1109/UEMCON.2017.8249039.
Luboš Brim & Jakub Chaloupka (2012):
Using strategy improvement to stay alive.
International Journal of Foundations of Computer Science 23(03),
pp. 585–608,
doi:10.1142/S0129054112400291.
Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini & Jean-François Raskin (2011):
Faster algorithms for mean-payoff games.
Formal Methods in System Design 38(2),
pp. 97–118,
doi:10.1007/s10703-010-0105-x.
Announced at MEMICS 2009 and GAMES 2009.
Karl Bringmann, Alejandro Cassis & Nick Fischer (2023):
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!.
arXiv preprint arXiv:2304.05279,
doi:10.48550/arXiv.2304.05279.
Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li & Frank Stephan (2022):
Deciding Parity Games in Quasi-polynomial Time.
SIAM Journal on Computing 51(2),
pp. 17–152,
doi:10.1137/17m1145288.
Announced at STOC 2017.
Pavol Cerný, Krishnendu Chatterjee, Thomas A. Henzinger, Arjun Radhakrishna & Rohit Singh (2011):
Quantitative Synthesis for Concurrent Programs.
In: Proc. of the 23rd International Conference on Computer Aided Verification (CAV 2011),
Lecture Notes in Computer Science 6806.
Springer,
pp. 243–259,
doi:10.1007/978-3-642-22110-1_20.
ArXiv:1104.4306.
Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger & Mariëlle Stoelinga (2003):
Resource Interfaces.
In: Rajeev Alur & Insup Lee: Proc. of the Third International Conference on Embedded Software (EMSOFT 2003),
Lecture Notes in Computer Science 2855.
Springer,
pp. 117–133,
doi:10.1007/978-3-540-45212-6_9.
Krishnendu Chatterjee, Laurent Doyen, Mickael Randour & Jean-François Raskin (2015):
Looking at mean-payoff and total-payoff through windows.
Inf. Comput. 242,
pp. 25–52,
doi:10.1016/j.ic.2015.03.010.
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger & Danupon Nanongkai (2014):
Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Algorithmica 70(3),
pp. 457–492,
doi:10.1007/s00453-013-9843-7.
ArXiv:1604.08234.
Announced at ESA 2012.
Carlo Comin & Romeo Rizzi (2017):
Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games.
Algorithmica 77(4),
pp. 995–1021,
doi:10.1007/s00453-016-0123-1.
Dani Dorfman, Haim Kaplan, Robert E. Tarjan & Uri Zwick (2023):
Optimal Energetic Paths for Electric Cars.
In: Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi & Grzegorz Herman: 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands,
LIPIcs 274.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
pp. 42:1–42:17,
doi:10.4230/LIPIcs.ESA.2023.42.
Dani Dorfman, Haim Kaplan & Uri Zwick (2019):
A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games.
In: Proc. of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 132,
pp. 114:1–114:14,
doi:10.4230/LIPIcs.ICALP.2019.114.
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.
Nathanaël Fijalkow, PawełGawrychowski & Pierre Ohlmann (2020):
Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games.
In: Proc. of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 170,
pp. 34:1–34:15,
doi:10.4230/LIPIcs.MFCS.2020.34.
Vladimir A. Gurvich, Alexander V. Karzanov & L. G. Khachivan (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.
Loïc Hélouët, Nicolas Markey & Ritam Raha (2019):
Reachability Games with Relaxed Energy Constraints.
In: Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019, Bordeaux, France, 2-3rd September 2019,
EPTCS 305,
pp. 17–33,
doi:10.4204/EPTCS.305.2.
Donald B. Johnson (1977):
Efficient Algorithms for Shortest Paths in Sparse Networks.
J. ACM 24(1),
pp. 1–13,
doi:10.1145/321992.321993.
Marcin Jurdziński (1998):
Deciding the winner in parity games is in UPco-UP.
Information Processing Letters 68(3),
pp. 119–124,
doi:10.1016/S0020-0190(98)00150-1.
Tomasz Kociumaka & Adam Polak (2023):
Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths.
In: Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi & Grzegorz Herman: 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands,
LIPIcs 274.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
pp. 72:1–72:10,
doi:10.4230/LIPIcs.ESA.2023.72.
ArXiv:2211.07325.
Donald A. Martin (1975):
Borel determinacy.
Annals of Mathematics 102(2),
pp. 363–371,
doi:10.2307/1971035.
Piotr Sankowski (2005):
Shortest Paths in Matrix Multiplication Time.
In: Gerth Stølting Brodal & Stefano Leonardi: Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings,
Lecture Notes in Computer Science 3669.
Springer,
pp. 770–778,
doi:10.1007/11561071_68.
Robert E. Tarjan (1972):
Depth-First Search and Linear Graph Algorithms.
SIAM J. Comput. 1(2),
pp. 146–160,
doi:10.1137/0201010.
Virginia Vassilevska Williams & R. Ryan Williams (2018):
Subcubic Equivalences Between Path, Matrix, and Triangle Problems.
J. ACM 65(5),
pp. 27:1–27:38,
doi:10.1145/3186893.
Announced at FOCS 2010.
Raphael Yuster & Uri Zwick (2005):
Answering distance queries in directed graphs using fast matrix multiplication.
In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings.
IEEE Computer Society,
pp. 389–396,
doi:10.1109/SFCS.2005.20.
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.
eptcs@eptcs.org