Bibliography

[1] M. H. Austern. Generic Programming and the STL. Professional computing series. Addison-Wesley, 1999.

[2] R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.

[3] T. F. Coleman, B. S. Garbow, and J. J. Moré. Algorithm 649: Fortran subroutines for estimating sparse hessian matrices. ACM Transactions on Mathematical Software, 11(4):378, December 1985.

[4] T. F. Coleman and J. J. Moré. Estimation of sparse jacobian matrices and graph coloring problems. SIAM Journal on Numerical Analysis, 20:187-209, 1984.

[5] T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

[6] A. Curtis, M. Powell, and J. Reid. On the estimation of sparse jacobian matrices. Journal of the Institute of Mathematics and its Applications, 13:117-119, 1974.

[7] E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.

[8] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

[9] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Professional Computing. Addison-Wesley, 1995.

[10] A. George, J. R. Gilbert, and J. W. Liu, editors. Graph Theory and Sparse Matrix Computation. Springer-Verlag New York, Inc, 1993.

[11] A. George and J. W.-H. Liu. Computer Solution of Large Sparse Positive Definite Systems. Computational Mathematics. Prentice-Hall, 1981.

[12] R. Graham and P. Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985.

[13] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.

[14] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. In Proceedings of the American Mathematical Society, volume 7, pages 48-50, 1956.

[15] D. Kühl. Design patterns for the implementation of graph algorithms. Master’s thesis, Technische Universität Berlin, July 1996.

[16] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, 1976.

[17] J. W. H. Liu. Modification of the minimum-degree algorithm by multiple elimination. ACM Transactions on Mathematical Software, 11(2):141-153, 1985.

[18] K. Mehlhorn and S. Näher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.

[19] N. C. Myers. Traits: a new and useful template technique. C++ Report, June 1995.

[20] R. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.

[21] Y. Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, 1996.

[22] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983.

[23] Seymour Parter. The use of linear graphs in Gauss elimination. SIAM Review, 3:119-130, 1961.

[24] D. Matula, G. Marble, and J. Isaacson. Graph coloring algorithms in Graph Theory and Computing. Academic Press, pp. 104-122, 1972.

[25] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.

[26] D. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. Computer Journal, 10:85-86, 1967.

[27] D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22:251-256, 1979.

[28] G. Heber, R. Biswas, and G. R. Gao. Self-Avoiding Walks over Adaptive Unstructured Grids. Parallel and Distributed Processing, LNCS 1586, Springer-Verlag, pp. 968-977, 1999.

[29] Esmond G. Ng and Padma Raghavan. Performance of greedy ordering heuristics for sparse Cholesky factorization. SIAM Journal on Matrix Analysis and Applications (to appear).

[30] Alan George and Joseph W. H. Liu. The Evolution of the Minimum Degree Ordering Algorithm. SIAM Review, 31(1):1-19, March 1989.

[31] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, pp. 399-404, 1956.

[32] A. V. Goldberg. A New Max-Flow Algorithm. MIT Technical Report MIT/LCS/TM-291, 1985.

[33] A. V. Karzanov. Determining the maximal flow in a network by the method of preflows. Soviet Mathematics Doklady, 1974.

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

[35] Jack Edmonds and Richard M. Karp. Theoretical improvements in the algorithmic efficiency for network flow problems. Journal of the ACM, 19:248-264, 1972.

[36] Robert E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972.

[37] David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic Graph Algorithms. Chapter 22, CRC Handbook of Algorithms and Theory of Computation, 1997.

[38] E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. Proceedings of the 24th National Conference of the ACM, 1969.

[39] J. Liu and A. Sherman. Comparative analysis of the Cuthill-McKee and the reverse Cuthill-McKee ordering algorithms for sparse matrices. SIAM Journal of Numerical Analysis, 13:198-213, 1975.

[40] Alan George. Computer implementation of the finite element method. Technical Report STAN-CS-208, Stanford University, 1971.

[41] Scott Fortin. The Graph Isomorphism Problem. TR 96-20, Dept. of Computer Science, University of Alberta, 1996.

[42] Brendan D. McKay. Practical Graph Isomorphism. Congressus Numerantium, 1981.

[43] Reingold, Nievergelt, and Deo. Combinatorial Algorithms: Theory and Practice. Prentice Hall, 1977.

[44] Edward Moore. The shortest path through a maze. International Symposium on the Theory of Switching, Harvard University Press, 1959.

[45] E. Nuutila. Efficient transitive closure computation in large digraphs. PhD Thesis, Helsinki University of Technology, 1995. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series, No. 74.

[46] A. Goralčíková and V. Koubek. A reduct and closure algorithm for graphs. In Mathematical Foundations of Computer Science, volume 74 of Lecture Notes in Computer Science, pages 301-307. Springer-Verlag, 1979.

[47] Klaus Simon. An Improved Algorithm for Transitive Closure on Acyclic Digraphs. Theoretical Computer Science 58 (Automata, Languages and Programming), 376-386, 1986.

[48] P. Purdom. A Transitive Closure Algorithm. BIT, 10:76-94, 1970.

[49] Ulrik Brandes. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, 25(2):163-177, 2001.

[50] Lindon C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40:35-41, 1977.

[51] J. M. Anthonisse. The rush in a directed graph. Technical Report BN9/71, Stichting Mathematisch Centrum, Amsterdam, 1971.

[52] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31:7-15, 1989.

[53] T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software. Practice & Experience, 21(11):1129-1164, 1991.

[54] Attila Gürsoy and Murat Atun. Neighborhood Preserving Load Balancing: A Self-Organizing Approach. Euro-Par Parallel Processing, LNCS 1900, pp. 324-341, 2000.

[55] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed Heaps: An alternative for Fibonacci Heaps with applications to parallel computation. Communications of the ACM, 31(11):1343-1354, November 1988.

[56] I. P. King. An automatic reordering scheme for simultaneous equations derived from network analysis. International Journal for Numerical Methods in Engineering, 2:523-533, 1970.

[57] C. Palmer and J. Steffan. Generating Network Topologies That Obey Power Laws. Proceedings of GLOBECOM, November 2000.

[58] J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965.

[59] Thomas Lengauer and Robert Endre Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-141, 1979.

[60] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco, 1997.

[61] Andrew W. Appel. Modern Compiler Implementation in Java. Cambridge University Press, 1998.

[62] Vladimir Kolmogorov. Graph Based Algorithms for Scene Reconstruction from Two or More Views. PhD thesis, Cornell University, September 2003.

[63] Yuri Boykov and Vladimir Kolmogorov. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. In IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9):1124-1137, September 2004.

[64] John M. Boyer and Wendy J. Myrvold. On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, 8(2):241-273, 2004.

[65] M. Chrobak and T. Payne. A Linear-time Algorithm for Drawing a Planar Graph on the Grid. Information Processing Letters, 54:241-246, 1995.

[66] H. de Fraysseix, J. Pach, and R. Pollack. How to Draw a Planar Graph on a Grid. Combinatorica, 10:41-51, 1990.

[67] David Bruce Wilson. Generating random spanning trees more quickly than the cover time. ACM Symposium on the Theory of Computing, pp. 296-303, 1996.

[68] J. Edmonds. Maximum Matching and a Polyhedron with 0, 1-Vertices. Journal of Research of the National Bureau of Standards B, 69:125-130, 1965.

[69] Harold N. Gabow. An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs. Journal of the ACM, 23(2):221-234, 1976.

[70] Harold N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434-443, 1990.

[71] Zvi Galil. Efficient Algorithms for Finding Maximum Matching in Graphs. ACM Computing Surveys, 18(1):23-38, 1986.

[72] J. Cochet-Terrasson et al. Numerical computation of spectral elements in max-plus algebra, 1998.

[73] A. Dasdan, S. S. Irani, and R. K. Gupta. Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio Problems. Proceedings of the 36th ACM/IEEE Design Automation Conference (DAC '99), 1999.

[74] K. Mehlhorn and C. Uhrig. The minimum cut algorithm of Stoer and Wagner, 1995.

[75] M. Stoer and F. Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, 1997.

[76] U. Zwick. Global minimum cuts, 2008.

[77] S. W. Sloan. An algorithm for profile and wavefront reduction of sparse matrices. International Journal for Numerical Methods in Engineering, 23:239-251, 1986.

[78] S. W. Sloan. A Fortran program for profile and wavefront reduction. International Journal for Numerical Methods in Engineering, 28:2651-2679, 1989.