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