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