Skip to content

Z. Bibliography

The works that the headers of the library cite, those that the README and NEWS name, and those that the chapters cite, in the alphabetical order of their first authors. The anchor of each entry is the key under which the chapters cite it.

Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin and Robert E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37(2):213–223, 1990. doi:10.1145/77600.77615

Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.

K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429–490, 1977. doi:10.1215/ijm/1256049011

Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958. doi:10.1090/qam/102435

Claude Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43(9):842–844, 1957. doi:10.1073/pnas.43.9.842

D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, Belmont, MA, 1997.

George E. P. Box and Mervin E. Muller. A note on the generation of random normal deviates. The Annals of Mathematical Statistics, 29(2):610–611, 1958. doi:10.1214/aoms/1177706645

J. M. Boyer and W. J. Myrvold. On the cutting edge: simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241–273, 2004. doi:10.7155/jgaa.00091

Ursula Bünnagel, Bernhard Korte and Jens Vygen. Efficient implementation of the Goldberg-Tarjan minimum-cost flow algorithm. Optimization Methods and Software, 10(2):157–174, 1998. doi:10.1080/10556789808805709

Cbc, the COIN-OR Branch and Cut solver. https://github.com/coin-or/Cbc

Joseph Cheriyan and S. N. Maheshwari. Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing, 18(6):1057–1086, 1989. doi:10.1137/0218072

Boris V. Cherkassky and Andrew V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4):390–410, 1997. doi:10.1007/PL00009180

N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976. Reprinted in Operations Research Forum, 3(1):20, 2022. doi:10.1007/s43069-021-00101-z

Yoeng-Jin Chu and Tseng-Hong Liu. On the shortest arborescence of a directed graph. Scientia Sinica, 14:1396–1400, 1965.

Clp, the COIN-OR Linear Programming solver. https://github.com/coin-or/Clp

Jean Cochet-Terrasson, Guy Cohen, Stéphane Gaubert, Michael McGettrick and Jean-Pierre Quadrat. Numerical computation of spectral elements in max-plus algebra. IFAC Proceedings Volumes, 31(18):667–674, 1998. doi:10.1016/S1474-6670(17)42067-2

COIN-OR, Computational Infrastructure for Operations Research. http://www.coin-or.org/

L. P. Cordella, P. Foggia, C. Sansone and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367–1372, 2004. doi:10.1109/TPAMI.2004.75

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001.

G. A. Croes. A method for solving traveling-salesman problems. Operations Research, 6(6):791–812, 1958. doi:10.1287/opre.6.6.791

William H. Cunningham. A network simplex method. Mathematical Programming, 11(1):105–116, 1976. doi:10.1007/BF01580379

George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.

Ali Dasdan. Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Transactions on Design Automation of Electronic Systems, 9(4):385–418, 2004. doi:10.1145/1027084.1027085

Ali Dasdan and Rajesh K. Gupta. Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(10):889–899, 1998. doi:10.1109/43.728912

Eric V. Denardo and Bennett L. Fox. Multichain Markov renewal programs. SIAM Journal on Applied Mathematics, 16(3):468–487, 1968. doi:10.1137/0116038

B. Dezső, A. Jüttner and P. Kovács. LEMON – an open source C++ graph template library. Electronic Notes in Theoretical Computer Science, 264(5):23–45, 2011. doi:10.1016/j.entcs.2011.06.003

Robert B. Dial. Algorithm 360: shortest-path forest with topological ordering. Communications of the ACM, 12(11):632–633, 1969. doi:10.1145/363269.363610

Reinhard Diestel. Graph Theory, 5th edition. Graduate Texts in Mathematics 173, Springer, 2017. doi:10.1007/978-3-662-53622-3

Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, 1959. doi:10.1007/BF01386390

Jack Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards, Section B, 69B(1–2):125–130, 1965. doi:10.6028/jres.069B.013

Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. doi:10.4153/CJM-1965-045-4

Jack Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B(4):233–240, 1967. doi:10.6028/jres.071B.032

Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248–264, 1972. doi:10.1145/321694.321699

EGRES, Egerváry Research Group on Combinatorial Optimization. http://www.cs.elte.hu/egres/

M. Englert, H. Röglin, and B. Vöcking. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica, 68(1):190–264, 2014. doi:10.1007/s00453-013-9801-4

Lester R. Ford and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. doi:10.4153/CJM-1956-045-5

Lester R. Ford, Jr. Network flow theory. Paper P-923, The RAND Corporation, Santa Monica, 1956.

Michael L. Fredman. On the efficiency of pairing heaps and related data structures. Journal of the ACM, 46(4):473–501, 1999. doi:10.1145/320211.320214

Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, 1987. doi:10.1145/28869.28874

Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator and Robert E. Tarjan. The pairing heap: a new form of self-adjusting heap. Algorithmica, 1(1):111–129, 1986. doi:10.1007/BF01840439

Harold N. Gabow, Zvi Galil, Thomas Spencer and Robert E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2):109–122, 1986. doi:10.1007/BF02579168

David Gale. A theorem on flows in networks. Pacific Journal of Mathematics, 7(2):1073–1082, 1957. doi:10.2140/pjm.1957.7.1073

Zvi Galil. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys, 18(1):23–38, 1986. doi:10.1145/6462.6502

Zvi Galil, Silvio Micali and Harold Gabow. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM Journal on Computing, 15(1):120–130, 1986. doi:10.1137/0215009

Tibor Gallai. Maximale Systeme unabhängiger Kanten. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 9:401–413, 1964.

M. R. Garey, D. S. Johnson and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267, 1976. doi:10.1016/0304-3975(76)90059-1

GLPK, the GNU Linear Programming Kit. https://www.gnu.org/software/glpk/

Andrew V. Goldberg. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22(1):1–29, 1997. doi:10.1006/jagm.1995.0805

Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921–940, 1988. doi:10.1145/48014.61051

Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM, 36(4):873–886, 1989. doi:10.1145/76359.76368

Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research, 15(3):430–466, 1990. doi:10.1287/moor.15.3.430

Ralph E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961. doi:10.1137/0109047

A. Grosso, M. Locatelli, and W. Pullan. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, 14(6):587–612, 2008. doi:10.1007/s10732-007-9055-x

Dan Gusfield. Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1):143–155, 1990. doi:10.1137/0219009

Horst W. Hamacher. A note on K best network flows. Annals of Operations Research, 57(1):65–72, 1995. doi:10.1007/BF02099691

Horst W. Hamacher, Jean-Claude Picard and Maurice Queyranne. On finding the K best cuts in a network. Operations Research Letters, 2(6):303–305, 1984. doi:10.1016/0167-6377(84)90083-X

J. Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. Journal of Algorithms, 17(3):424–446, 1994. doi:10.1006/jagm.1994.1043

Peter E. Hart, Nils J. Nilsson and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136

Mark Hartmann and James B. Orlin. Finding minimum cost to time ratio cycles with small integral transit times. Networks, 23(6):567–574, 1993. doi:10.1002/net.3230230607

P. J. Heawood. Map-colour theorem. The Quarterly Journal of Pure and Applied Mathematics, 24:332–338, 1890.

C. Hierholzer and C. Wiener. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6(1):30–32, 1873. doi:10.1007/BF01442866

Alan J. Hoffman. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics, 10:113–127, 1960. doi:10.1090/psapm/010/0114759

J. Hopcroft and R. Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372–378, 1973. doi:10.1145/362248.362272

John E. Hopcroft and Richard M. Karp. An n^{5/2} algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225–231, 1973. doi:10.1137/0202019

Ronald A. Howard. Dynamic Programming and Markov Processes. MIT Press, 1960.

D. S. Johnson and C. C. McGeoch (editors). Network Flows and Matching: First DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 12. American Mathematical Society, 1993. doi:10.1090/dimacs/012

Donald B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters, 4(3):53–57, 1975. doi:10.1016/0020-0190(75)90001-0

A. Jüttner and P. Madarasi. VF2++: an improved subgraph isomorphism algorithm. Discrete Applied Mathematics, 242:69–81, 2018. doi:10.1016/j.dam.2018.02.018

Richard M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3):309–311, 1978. doi:10.1016/0012-365X(78)90011-0

Damian J. Kelly and Garrett M. O'Neill. The Minimum Cost Flow Problem and The Network Simplex Method. Master's thesis, University College, Dublin, 1991.

A. B. Kempe. On the geographical problem of the four colours. American Journal of Mathematics, 2(3):193–200, 1879. doi:10.2307/2369235

Zoltán Király and Péter Kovács. Efficient implementations of minimum-cost flow algorithms. Acta Universitatis Sapientiae, Informatica, 4:67–118, 2012.

Morton Klein. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science, 14(3):205–220, 1967. doi:10.1287/mnsc.14.3.205

Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, 1969.

Dénes König. Gráfok és mátrixok. Matematikai és Fizikai Lapok, 38:116–119, 1931.

Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50, 1956. doi:10.1090/S0002-9939-1956-0078686-7

C. Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15:271–283, 1930. doi:10.4064/fm-15-1-271-283

Eugene L. Lawler. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7):401–405, 1972. doi:10.1287/mnsc.18.7.401

George Marsaglia and Thomas A. Bray. A convenient method for generating normal variables. SIAM Review, 6(3):260–264, 1964. doi:10.1137/1006063

Makoto Matsumoto and Takuji Nishimura. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8(1):3–30, 1998. doi:10.1145/272991.272995

David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427, 1983. doi:10.1145/2402.322385

B. D. McKay and A. Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94–112, 2014. doi:10.1016/j.jsc.2013.09.003

Karl Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10:96–115, 1927. doi:10.4064/fm-10-1-96-115

Katta G. Murty. Solving the fixed charge problem by ranking the extreme points. Operations Research, 16(2):268–279, 1968. doi:10.1287/opre.16.2.268

Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54–66, 1992. doi:10.1137/0405004

Seth Pettie. Towards a final analysis of pairing heaps. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pages 174–183, 2005. doi:10.1109/SFCS.2005.75

Jean-Claude Picard and Maurice Queyranne. On the structure of all minimum cuts in a network and applications. Mathematical Programming Study, 13:8–16, 1980. doi:10.1007/BFb0120902

Ira Pohl. Bi-directional search. Machine Intelligence, 6:127–140, 1971.

Wayne Pullan and Holger H. Hoos. Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 25:159–185, 2006. doi:10.1613/jair.1815

D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563–581, 1977. doi:10.1137/0206041

W. Schnyder. Embedding planar graphs on the grid. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90), 138–148, 1990.

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, 2003.

M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1):67–72, 1981. doi:10.1016/0898-1221(81)90008-0

D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652–686, 1985. doi:10.1145/3828.3835

SoPlex, the Sequential object-oriented simPlex. https://soplex.zib.de/

Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585–591, 1997. doi:10.1145/263867.263872

IBM ILOG CPLEX Optimization Studio. https://www.ibm.com/products/ilog-cplex-optimization-studio

John W. Suurballe. Disjoint paths in a network. Networks, 4(2):125–145, 1974. doi:10.1002/net.3230040204

John W. Suurballe and Robert E. Tarjan. A quick method for finding shortest pairs of disjoint paths. Networks, 14(2):325–336, 1984. doi:10.1002/net.3230140209

Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146–160, 1972. doi:10.1137/0201010

Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215–225, 1975. doi:10.1145/321879.321884

Robert E. Tarjan. Data Structures and Network Algorithms. SIAM, 1983. doi:10.1137/1.9781611970265

Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984. doi:10.1145/62.2160

Robert E. Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566–579, 1984. doi:10.1137/0213035

E. Tomita and T. Seki. An efficient branch-and-bound algorithm for finding a maximum clique. In Discrete Mathematics and Theoretical Computer Science (DMTCS 2003), Lecture Notes in Computer Science, volume 2731, pages 278–289. Springer, 2003. doi:10.1007/3-540-45066-1_22

N. Tomizawa. On some techniques useful for solution of transportation network problems. Networks, 1(2):173–194, 1971. doi:10.1002/net.3230010206

William T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, s1–22(2):107–111, 1947. doi:10.1112/jlms/s1-22.2.107

Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21(4):309–315, 1978. doi:10.1145/359460.359478

J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347–348, 1964. doi:10.1145/512274.3734138