@article{EdmondsPaths,
  author       = {Edmonds, Jack},
  title        = {Paths, Trees, and Flowers},
  journal      = {Canadian Journal of Mathematics},
  volume       = {17},
  pages        = {449--467},
  year         = {1965},
  doi          = {10.4153/CJM-1965-045-4},
  url          = {https://doi.org/10.4153/CJM-1965-045-4}
}

@inproceedings{MicaliVazirani,
  author       = {Micali, Silvio and Vazirani, Vijay V.},
  title        = {An {$O(\sqrt{|V|}\,|E|)$} Algorithm for Finding
                  Maximum Matching in General Graphs},
  booktitle    = {21st Annual Symposium on Foundations of Computer Science},
  pages        = {17--27},
  publisher    = {IEEE},
  year         = {1980},
  doi          = {10.1109/SFCS.1980.12},
  url          = {https://ics.uci.edu/~vazirani/MV.pdf}
}

@article{MicaliVaziraniAnalysis,
  author       = {Vazirani, Vijay V.},
  title        = {A Theory of Alternating Paths and Blossoms from the
                  Perspective of Minimum Length},
  journal      = {Mathematics of Operations Research},
  volume       = {49},
  number       = {3},
  pages        = {2009--2047},
  year         = {2024},
  doi          = {10.1287/moor.2020.0388},
  url          = {https://ics.uci.edu/~vazirani/Matching_paper.pdf},
  note         = {Corrected version of record, updated November 15, 2024}
}

@inproceedings{FlowRandomized,
  author       = {Chen, Li and Kyng, Rasmus and Liu, Yang P. and Peng, Richard
                  and Probst Gutenberg, Maximilian and Sachdeva, Sushant},
  title        = {Maximum Flow and Minimum-Cost Flow in Almost-Linear Time},
  booktitle    = {2022 IEEE 63rd Annual Symposium on Foundations of
                  Computer Science (FOCS)},
  pages        = {612--623},
  publisher    = {IEEE},
  year         = {2022},
  doi          = {10.1109/FOCS54457.2022.00064},
  url          = {https://arxiv.org/abs/2203.00671v2},
  note         = {Full version: arXiv:2203.00671v2}
}

@misc{FlowDeterministic,
  author       = {van den Brand, Jan and Chen, Li and Kyng, Rasmus
                  and Liu, Yang P. and Peng, Richard
                  and Probst Gutenberg, Maximilian
                  and Sachdeva, Sushant and Sidford, Aaron},
  title        = {A Deterministic Almost-Linear Time Algorithm for
                  Minimum-Cost Flow},
  year         = {2023},
  eprint       = {2309.16629},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi          = {10.48550/arXiv.2309.16629},
  url          = {https://arxiv.org/abs/2309.16629v1},
  note         = {arXiv:2309.16629v1; full version of the FOCS 2023 paper}
}

@misc{IncrementalGraphs,
  author       = {Chen, Li and Kyng, Rasmus and Liu, Yang P.
                  and Meierhans, Simon and Probst Gutenberg, Maximilian},
  title        = {Almost-Linear Time Algorithms for Incremental Graphs:
                  Cycle Detection, {SCCs}, {$s$--$t$} Shortest Path,
                  and Minimum-Cost Flow},
  year         = {2023},
  eprint       = {2311.18295},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi          = {10.48550/arXiv.2311.18295},
  url          = {https://arxiv.org/abs/2311.18295v1},
  note         = {arXiv:2311.18295v1}
}

@article{TroppBernstein,
  author       = {Tropp, Joel A.},
  title        = {User-Friendly Tail Bounds for Sums of Random Matrices},
  journal      = {Foundations of Computational Mathematics},
  volume       = {12},
  number       = {4},
  pages        = {389--434},
  year         = {2012},
  doi          = {10.1007/s10208-011-9099-z},
  url          = {https://arxiv.org/abs/1004.4389v7},
  note         = {arXiv:1004.4389v7}
}

@article{DynamicTrees,
  author       = {Sleator, Daniel D. and Tarjan, Robert Endre},
  title        = {A Data Structure for Dynamic Trees},
  journal      = {Journal of Computer and System Sciences},
  volume       = {26},
  number       = {3},
  pages        = {362--391},
  year         = {1983},
  doi          = {10.1016/0022-0000(83)90006-5},
  url          = {https://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/dynamic-trees.pdf}
}

@article{PermutationNetworks,
  author       = {Bene{\v{s}}, V. E.},
  title        = {Optimal Rearrangeable Multistage Connecting Networks},
  journal      = {Bell System Technical Journal},
  volume       = {43},
  number       = {4},
  pages        = {1641--1656},
  year         = {1964},
  doi          = {10.1002/j.1538-7305.1964.tb04103.x},
  url          = {https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1964.tb04103.x}
}

@article{Berge1957,
  author = {Berge, Claude},
  title = {Two Theorems in Graph Theory},
  journal = {Proceedings of the National Academy of Sciences of the United States of America},
  volume = {43}, number = {9}, pages = {842--844}, year = {1957},
  doi = {10.1073/pnas.43.9.842},
  url = {https://doi.org/10.1073/pnas.43.9.842}
}

@article{Tutte1947,
  author = {Tutte, W. T.},
  title = {The Factorization of Linear Graphs},
  journal = {Journal of the London Mathematical Society},
  volume = {s1-22}, number = {2}, pages = {107--111}, year = {1947},
  doi = {10.1112/jlms/s1-22.2.107},
  url = {https://doi.org/10.1112/jlms/s1-22.2.107}
}

@article{Tutte1954Factor,
  author = {Tutte, W. T.},
  title = {A Short Proof of the Factor Theorem for Finite Graphs},
  journal = {Canadian Journal of Mathematics},
  volume = {6}, pages = {347--352}, year = {1954},
  doi = {10.4153/CJM-1954-033-3},
  url = {https://doi.org/10.4153/CJM-1954-033-3}
}

@article{EdmondsPolytope,
  author = {Edmonds, Jack},
  title = {Maximum Matching and a Polyhedron With {$0,1$}-Vertices},
  journal = {Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics},
  volume = {69B}, number = {1--2}, pages = {125--130}, year = {1965},
  url = {https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf}
}

@article{HopcroftKarp1973,
  author = {Hopcroft, John E. and Karp, Richard M.},
  title = {An {$n^{5/2}$} Algorithm for Maximum Matchings in Bipartite Graphs},
  journal = {SIAM Journal on Computing},
  volume = {2}, number = {4}, pages = {225--231}, year = {1973},
  doi = {10.1137/0202019}, url = {https://doi.org/10.1137/0202019}
}

@incollection{Karzanov1973Representatives,
  author = {Karzanov, A. V.},
  title = {An Exact Estimate of an Algorithm for Finding a Maximum Flow,
           Applied to the Problem ``On Representatives''},
  booktitle = {Voprosy Kibernetiki. Trudy Seminara po Kombinatornoi Matematike
               (Moscow, 1971)},
  publisher = {Sovetskoe Radio}, address = {Moscow},
  pages = {66--70}, year = {1973},
  note = {In Russian; English translation by the author},
  url = {https://alexander-karzanov.net/ScannedOld/73_tochn-ots_transl.pdf}
}

@article{GoldbergKarzanov2004,
  author = {Goldberg, Andrew V. and Karzanov, Alexander V.},
  title = {Maximum Skew-Symmetric Flows and Matchings},
  journal = {Mathematical Programming},
  volume = {100}, number = {3}, pages = {537--568}, year = {2004},
  doi = {10.1007/s10107-004-0505-z},
  url = {https://arxiv.org/abs/math/0304290v2}
}

@article{Gabow2025FMatching,
  author = {Gabow, Harold N.},
  title = {Maximum Cardinality {$f$}-Matching in Time {$O(n^{2/3}m)$}},
  journal = {ACM Transactions on Algorithms},
  volume = {21}, number = {1}, articleno = {9},
  pages = {9:1--9:28}, numpages = {28}, year = {2025},
  doi = {10.1145/3696668},
  url = {https://arxiv.org/abs/2311.14236v1},
  note = {Published online December 2, 2024}
}

@article{GabowTarjan1991,
  author = {Gabow, Harold N. and Tarjan, Robert E.},
  title = {Faster Scaling Algorithms for General Graph-Matching Problems},
  journal = {Journal of the ACM},
  volume = {38}, number = {4}, pages = {815--853}, year = {1991},
  doi = {10.1145/115234.115366},
  url = {https://doi.org/10.1145/115234.115366}
}

@article{Gabow2017,
  author = {Gabow, Harold N.},
  title = {The Weighted Matching Approach to Maximum Cardinality Matching},
  journal = {Fundamenta Informaticae},
  volume = {154}, number = {1--4}, pages = {109--130}, year = {2017},
  doi = {10.3233/FI-2017-1555}, url = {https://arxiv.org/abs/1703.03998}
}

@inproceedings{Lovasz1979,
  author = {Lov{\'a}sz, L{\'a}szl{\'o}},
  title = {On Determinants, Matchings, and Random Algorithms},
  editor = {Budach, Lothar},
  booktitle = {Fundamentals of Computation Theory, FCT '79},
  publisher = {Akademie-Verlag}, address = {Berlin},
  pages = {565--574}, year = {1979},
  url = {https://www.math.uwaterloo.ca/~harvey/W11/1979-Lovasz-OnDeterminantsMatchingsAndRandomAlgs.pdf}
}

@inproceedings{MuchaSankowski2004,
  author = {Mucha, Marcin and Sankowski, Piotr},
  title = {Maximum Matchings via {Gaussian} Elimination},
  booktitle = {45th Annual IEEE Symposium on Foundations of Computer Science},
  publisher = {IEEE}, pages = {248--255}, year = {2004},
  doi = {10.1109/FOCS.2004.40},
  url = {https://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf}
}

@article{Harvey2009,
  author = {Harvey, Nicholas J. A.},
  title = {Algebraic Algorithms for Matching and Matroid Problems},
  journal = {SIAM Journal on Computing},
  volume = {39}, number = {2}, pages = {679--702}, year = {2009},
  doi = {10.1137/070684008}, url = {https://doi.org/10.1137/070684008}
}

@article{DuanPettieSu2018,
  author = {Duan, Ran and Pettie, Seth and Su, Hsin-Hao},
  title = {Scaling Algorithms for Weighted Matching in General Graphs},
  journal = {ACM Transactions on Algorithms},
  volume = {14},
  number = {1},
  articleno = {8},
  numpages = {35},
  pages = {8:1--8:35},
  month = jan,
  year = {2018},
  doi = {10.1145/3155301},
  url = {https://doi.org/10.1145/3155301},
  eprint = {1411.1919},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS}
}

@misc{Madry2013CentralPath,
  author = {Aleksander M{\k{a}}dry},
  title = {Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back},
  year = {2013},
  eprint = {1307.2205},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.1307.2205},
  url = {https://arxiv.org/abs/1307.2205v3},
  note = {FOCS 2013; full version 3, October 24, 2013}
}

@inproceedings{vanDenBrandEtAl2020BipartiteMatching,
  author = {van den Brand, Jan and Lee, Yin-Tat and Nanongkai, Danupon and Peng, Richard and Saranurak, Thatchaphol and Sidford, Aaron and Song, Zhao and Wang, Di},
  title = {Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs},
  booktitle = {2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)},
  pages = {919--930},
  publisher = {IEEE},
  year = {2020},
  doi = {10.1109/FOCS46700.2020.00090},
  url = {https://doi.org/10.1109/FOCS46700.2020.00090},
  eprint = {2009.01802},
  archivePrefix = {arXiv}
}

@article{Hall1935,
  author = {Hall, Philip},
  title = {On Representatives of Subsets},
  journal = {Journal of the London Mathematical Society},
  volume = {s1-10},
  number = {1},
  pages = {26--30},
  year = {1935},
  doi = {10.1112/jlms/s1-10.37.26},
  url = {https://doi.org/10.1112/jlms/s1-10.37.26}
}

@article{FordFulkerson1958,
  author = {Ford, Jr., L. R. and Fulkerson, D. R.},
  title = {Network Flow and Systems of Representatives},
  journal = {Canadian Journal of Mathematics},
  volume = {10},
  pages = {78--84},
  year = {1958},
  doi = {10.4153/CJM-1958-009-1},
  url = {https://doi.org/10.4153/CJM-1958-009-1}
}

@article{Gale1957,
  author = {Gale, David},
  title = {A Theorem on Flows in Networks},
  journal = {Pacific Journal of Mathematics},
  volume = {7},
  number = {2},
  pages = {1073--1082},
  year = {1957},
  url = {https://msp.org/pjm/1957/7-2/pjm-v7-n2-p04-p.pdf}
}

@inproceedings{KhandekarRaoVazirani2006,
  author = {Khandekar, Rohit and Rao, Satish and Vazirani, Umesh V.},
  title = {Graph Partitioning Using Single Commodity Flows},
  booktitle = {Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing},
  year = {2006},
  pages = {385--390},
  publisher = {ACM},
  doi = {10.1145/1132516.1132574},
  url = {https://people.eecs.berkeley.edu/~vazirani/pubs/partitioning.pdf}
}

@article{SinclairJerrum1989,
  author = {Sinclair, Alistair and Jerrum, Mark},
  title = {Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains},
  journal = {Information and Computation},
  volume = {82},
  number = {1},
  pages = {93--133},
  year = {1989},
  doi = {10.1016/0890-5401(89)90067-9},
  url = {https://people.eecs.berkeley.edu/~sinclair/approx.pdf}
}

@inproceedings{GhaffariKuhnSu2017,
  author = {Ghaffari, Mohsen and Kuhn, Fabian and Su, Hsin-Hao},
  title = {Distributed {MST} and Routing in Almost Mixing Time},
  booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  pages = {131--140},
  publisher = {ACM},
  year = {2017},
  doi = {10.1145/3087801.3087827},
  url = {https://groups.csail.mit.edu/tds/papers/Ghaffari/podc117.pdf}
}

@inproceedings{RandomShifts,
  author = {Miller, Gary L. and Peng, Richard and Xu, Shen Chen},
  title = {Parallel Graph Decompositions Using Random Shifts},
  booktitle = {Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures},
  year = {2013},
  pages = {196--203},
  doi = {10.1145/2486159.2486180},
  url = {https://arxiv.org/abs/1307.3692}
}

@misc{MinorAggregateRouting,
  author = {Rozho{\v{n}}, V{\'a}clav and Grunau, Christoph and Haeupler, Bernhard and Zuzic, Goran and Li, Jason},
  title = {Undirected {$(1+\varepsilon)$}-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel \& Distributed Algorithms},
  year = {2022},
  eprint = {2204.05874},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  url = {https://arxiv.org/abs/2204.05874v2},
  note = {Version 2, September 23, 2022; author order randomized}
}

@misc{MinRatioDistanceOracles2026,
  author = {Kyng, Rasmus and Meierhans, Simon and Probst Gutenberg, Maximilian and Sulser, Aurelio},
  title = {A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles},
  year = {2026},
  eprint = {2609.23852},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  url = {https://arxiv.org/abs/2609.23852v1},
  note = {Version 1, September 20, 2026}
}

@article{DahlhausKarpinski,
  author = {Dahlhaus, Elias and Karpinski, Marek},
  title = {Perfect Matching for Regular Graphs Is {$AC^0$}-Hard for the General Matching Problem},
  journal = {Journal of Computer and System Sciences},
  volume = {44},
  number = {1},
  pages = {94--102},
  year = {1992},
  doi = {10.1016/0022-0000(92)90005-4},
  url = {https://doi.org/10.1016/0022-0000(92)90005-4}
}

@article{LevinUniversal,
  author = {Levin, Leonid A.},
  title = {Universal Sequential Search Problems},
  journal = {Problems of Information Transmission},
  volume = {9},
  number = {3},
  pages = {265--266},
  year = {1973},
  url = {https://www.mathnet.ru/eng/ppi914},
  note = {Russian original in Problemy Peredachi Informatsii 9(3), 115--116}
}

@article{SplayTrees1985,
  author = {Sleator, Daniel Dominic and Tarjan, Robert Endre},
  title = {Self-Adjusting Binary Search Trees},
  journal = {Journal of the ACM},
  volume = {32},
  number = {3},
  pages = {652--686},
  year = {1985},
  doi = {10.1145/3828.3835},
  url = {https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf}
}

@inproceedings{BrandLiuSidford2023,
  author = {van den Brand, Jan and Liu, Yang P. and Sidford, Aaron},
  title = {Dynamic Maxflow via Dynamic Interior Point Methods},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing},
  year = {2023},
  pages = {1215--1228},
  publisher = {ACM},
  doi = {10.1145/3564246.3585135},
  eprint = {2212.06315},
  archivePrefix = {arXiv},
  note = {Full version: arXiv:2212.06315v1}
}

@misc{KyngMeierhansProbstGutenberg2023FlatForest,
  author = {Kyng, Rasmus and Meierhans, Simon and Probst Gutenberg, Maximilian},
  title = {A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications},
  year = {2023},
  month = nov,
  eprint = {2311.06402},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.2311.06402},
  url = {https://arxiv.org/abs/2311.06402v1},
  note = {Version 1, November 10, 2023}
}