Bibliography

1

A. V. Aho, J. E. Hopcroft, and J. D. Ullman.
Data Structures and Algorithms.
Addison-Wesley, 1983.

2

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

3

G. Baumgartner and V. F. Russo.
Signatures: A language extension for improving type abstraction and subtype polymorphism in C++.
Software-Practice and Experience, 25(8):863-889, August 1995.

4

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

5

K. B. Bruce, L. Cardelli, G. Castagna, the Hopkins Objects Group, G. T. Leavens, and B. Pierce.
On binary methods.
Theory and Practice of Object Systems, 1:221-242, 1995.

6

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

7

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

8

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

9

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.

10

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

11

L. R. Ford and D. R. Fulkerson.
Flows in networks.
Princeton University Press, 1962.

12

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

13

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

14

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

15

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.

16

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.

18

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

19

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

20

E. L. Lawler.
Combinatorial Opimization: Networks and Matroids.
Holt, Rinehart, and Winston, 1976.

21

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

22

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

23

B. Meyer.
Object-oriented Software Construction.
Prentice Hall International Series in Computer Science. Prentice Hall, 1988.

24

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

25

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

26

Y. Saad.
Iterative Methods for Sparse Minear System.
PWS Publishing Company, 1996.

27

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

28

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

29

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

30

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

31

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

32

D. Br'elaz
New methods to color the vertices of a graph
Communications of the ACM, vol. 22, 1979, pp. 251-256.

33

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

34

Esmond G. Ng amd Padma Raghavan
Performance of greedy ordering heuristics for sparse {C}holesky factorization
SIAM Journal on Matrix Analysis and Applications (To appear)

35

Alan George and Joseph W. H. Liu
The Evolution of the Minimum Degree Ordering Algorithm
SIAM Review, March 1989, vol. 31, num. 1, pp. 1-19.

36

L. R. Ford and D. R. Fulkerson
Maximal flow through a network.
Can. Journal of Mathematics 1956 pp.399-404

37

A. V. Goldberg
A New Max-Flow Algorithm.
MIT Tehnical report MIT/LCS/TM-291, 1985.

38

A. V. Karzanov
Determining the maximal flow in a network by the method of preflows.
Sov. Math. Dokl. 1974

39

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

40

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

41

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

42

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

43

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

44

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 (1975), pp. 198-213.

45

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

46

Scott Fortin
The Graph Isomorphism Problem
TR 96-20, Dept. of Computer Science, University of Alberta (1996)

47

Brendan D. McKay
Practical Graph Isomorphism
Congressus Numerantium (1981)

48

Reingold, Nievergelt, and Deo
Combinatorial Algorithms: Theory and Practice
Prentice Hall (1977)

49

Edward Moore
The shortest path through a maze
International Symposium on the Theory of Switching (1959)
Harvard University Press

50

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.

51

A. Goralcikova 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

52

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

53

P. Purdom
A Transitive Closure Algorithm
BIT, 10, 1970, pp. 76-94.

54

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

55

Lindon C. Freeman
A Set of Measures of Centrality Based on Betweenness
Sociometry 40, pp. 35-41, 1977.

56

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

57

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

58

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

59

Thomas F. Coleman and Jorge J. More
Estimation of sparse Jacobian matrices and graph coloring problems.
Journal of Numerical Analasis V20, pp. 187-209, 1983.

60

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

61

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), pp. 1343-1354, November 1988.

62

King, I. P.
An automatic reordering scheme for simultaneous equations derived from network analysis.
Int. J. Numer. Methods Engrg. 2, pp. 523-533, 1970.

63

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

64

J. Edmonds
Paths, trees, and flowers
Canadian Journal of Mathematics 17 (1965), pp. 449-467.

65

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

66

Steven S. Muchnick
Advanced Compiler Design and Implementation
Morgan Kaufmann Publishers, San Fransisco, 1997.

67

Andrew W. Appel
Modern Compiler Implementation in JAVA
Cambridge University Press, 1998.

68

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

69

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, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.

70

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.

71

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

72

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

73

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

74

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

75

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

76

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.