The Algorithm Design Manual Second Edition

Symposium on Algorithms (ESA’04), pages 664–676, 2004.

[Gab76]

H. Gabow. An efficient implementation of Edmond’s algorithm for maxi-

mum matching on graphs. J. ACM, 23:221–234, 1976.

[Gab77]

H. Gabow. Two algorithms for generating weighted spanning trees in order.

SIAM J. Computing, 6:139–150, 1977.

[Gal86]

Z. Galil. Efficient algorithms for finding maximum matchings in graphs.

ACM Computing Surveys, 18:23–38, 1986.

[Gal90]

K. Gallivan. Parallel Algorithms for Matrix Computations. SIAM, Philadel-

phia, 1990.

[Gas03]

S. Gass. Linear Programming: Methods and Applications. Dover, fifth edi-

tion, 2003.

[GBDS80]

B. Golden, L. Bodin, T. Doyle, and W. Stewart. Approximate traveling

salesman algorithms. Operations Research, 28:694–711, 1980.

[GBY91]

G. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Struc-

tures. Addison-Wesley, Wokingham, England, second edition, 1991.

[Gen04]

J. Gentle. Random Number Generation and Monte Carlo Methods. Springer,

second edition, 2004.

[GGJ77]

M. Garey, R. Graham, and D. Johnson. The complexity of computing

Steiner minimal trees. SIAM J. Appl. Math., 32:835–859, 1977.

[GGJK78]

M. Garey, R. Graham, D. Johnson, and D. Knuth. Complexity results for

bandwidth minimization. SIAM J. Appl. Math., 34:477–495, 1978.

[GH85]

R. Graham and P. Hell. On the history of the minimum spanning tree

problem. Annals of the History of Computing, 7:43–57, 1985.

[GH06]

P. Galinier and A. Hertz. A survey of local search methods for graph color-

ing. Computers and Operations Research, 33:2547–2562, 2006.

[GHMS93]

L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink. Ap-

proximating polygons and subdivisions with minimum link paths. Internat.

J. Comput. Geom. Appl., 3(4):383–415, December 1993.

[GHR95]

R. Greenlaw, J. Hoover, and W. Ruzzo. Limits to Parallel Computation:

P-completeness theory. Oxford University Press, New York, 1995.

---

B I B L I O G R A P H Y

681

[GI89]

D. Gusfield and R. Irving. The Stable Marriage Problem: structure and al-

gorithms. MIT Press, Cambridge MA, 1989.

[GI91]

Z. Galil and G. Italiano. Data structures and algorithms for disjoint set

union problems. ACM Computing Surveys, 23:319–344, 1991.

[Gib76]

N. E. Gibbs. A hybrid profile reduction algorithm. ACM Trans. Math.

Softw., 2(4):378–387, December 1976.

[Gib85]

A. Gibbons. Algorithmic Graph Theory. Cambridge Univ. Press, 1985.

[GJ77]

M. Garey and D. Johnson. The rectilinear Steiner tree problem is NP-

complete. SIAM J. Appl. Math., 32:826–834, 1977.

[GJ79]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to

the theory of NP-completeness. W. H. Freeman, San Francisco, 1979.

[GJM02]

M. Goldwasser, D. Johnson, and C. McGeoch, editors. Data Structures,

Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Imple-

mentation Challenges, volume 59. AMS, Providence RI, 2002.

[GJPT78]

M. Garey, D. Johnson, F. Preparata, and R. Tarjan. Triangulating a simple

polygon. Info. Proc. Letters, 7:175–180, 1978.

[GK95]

A. Goldberg and R. Kennedy. An efficient cost scaling algorithm for the

assignment problem. Math. Programming, 71:153–177, 1995.

[GK98]

S. Guha and S. Khuller. Approximation algorithms for connected dominat-

ing sets. Algorithmica, 20:374–387, 1998.

[GKK74]

F. Glover, D. Karney, and D. Klingman. Implementation and computational

comparisons of primal-dual computer codes for minimum-cost network flow

problems. Networks, 4:191–212, 1974.

[GKP89]

R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics. Addison-

Wesley, Reading MA, 1989.

[GKS95]

S. Gupta, J. Kececioglu, and A. Sch¨

affer. Improving the practical space

and time efficiency of the shortest-paths approach to sum-of-pairs multiple

sequence alignment. J. Computational Biology, 2:459–472, 1995.

[GKT05]

D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs

in massive graphs. In Proc. 31st Int. Conf on Very Large Data Bases, pages

721–732, 2005.

[GKW06]

A. Goldberg, H. Kaplan, and R. Werneck. Reach for A