References

AB95

D. Avis and D. Bremner. How good are convex hull algorithms? In Proc. 11th Annual ACM Symposium on Computational Geometry, pages 20-28, 1995.

ABCC95

D. Applegate, R. Bixby, V. Chvatal, and W. Cook. Finding cuts in the TSP (a preliminary report). Technical Report 95-05, DIMACS, Rutgers University, Piscataway NJ, 1995.

Abd80

N. N. Abdelmalek. A Fortran subroutine for the solution of overdetermined systems of linear equations. ACM Trans. Math. Softw., 6(2):228-230, June 1980.

AC75

A. Aho and M. Corasick. Efficient string matching: an aid to bibliographic search. Communications of the ACM, 18:333-340, 1975.

AC91

D. Applegate and W. Cook. A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3:149-156, 1991.

ACH 91

E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. An efficiently computable metric for comparing polygonal shapes. IEEE Trans. PAMI, 13(3):209-216, 1991.

ACI92

D. Alberts, G. Cattaneo, and G. Italiano. An empirical study of dynamic graph algorithms. In Proc. Seventh ACM-SIAM Symp. Discrete Algorithms (SODA), pages 192-201, 1992.

ADKF70

V. Arlazarov, E. Dinic, M. Kronrod, and I. Faradzev. On economical construction of the transitive closure of a directed graph. Soviet Mathematics, Doklady, 11:1209-1210, 1970.

Adl94a

L. Adleman. Algorithmic number theory - the complexity contribution. In Proc. 35th IEEE Symp. Foundations of Computer Science (FOCS), pages 88-113, 1994.

Adl94b

L. M. Adleman. Molecular computations of solutions to combinatorial problems. Science, 266:1021-1024, November 11, 1994.

AE83

D. Avis and H. ElGindy. A combinatorial approach to polygon similarity. IEEE Trans. Inform. Theory, IT-2:148-150, 1983.

AF92

D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom., 8:295-313, 1992.

AG86

A. Apostolico and R. Giancarlo. The Boyer-Moore-Galil string searching strategies revisited. SIAM J. Computing, 15:98-105, 1986.

AGSS89

A. Aggarwal, L. Guibas, J. Saxe, and P. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete and Computational Geometry, 4:591-604, 1989.

AGU72

A. Aho, M. Garey, and J. Ullman. The transitive reduction of a directed graph. SIAM J. Computing, 1:131-137, 1972.

Aho90

A. Aho. Algorithms for finding patterns in strings. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 255-300. MIT Press, 1990.

AHU74

A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading MA, 1974.

AHU83

A. Aho, J. Hopcroft, and J. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading MA, 1983.

Aig88

M. Aigner. Combinatorial Search. Wiley-Teubner, 1988.

AK89

E. Aarts and J. Korst. Simulated annealing and Boltzman machines: A stochastic approach to combinatorial optimization and neural computing. John Wiley and Sons, 1989.

AKD83

J. H. Ahrens, K. D. Kohrt, and U. Dieter. Sampling from gamma and Poisson distributions. ACM Trans. Math. Softw., 9(2):255-257, June 1983.

AM93

S. Arya and D. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proc. Fourth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 271-280, 1993.

AMN 94

S. Arya, D. Mount, N. Netanyahu, R. Silverman, and A. Wu. Approximate nearest neighbor queries in fixed dimensions. In Proc. Fifth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 573-582, 1994.

AMO93

R. Ahuja, T. Magnanti, and J. Orlin. Network Flows. Prentice Hall, Englewood Cliffs NJ, 1993.

AMOT88

R. Ahuja, K. Mehlhorn, J. Orlin, and R. Tarjan. Faster algorithms for the shortest path problem. Technical Report 193, MIT Operations Research Center, 1988.

AMWW88

H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl. Congruence, similarity and symmetries of geometric objects. Discrete Comput. Geom., 3:237-256, 1988.

And76

G. Andrews. The Theory of Partitions. Addison-Wesley, Reading, Mass., 1976.

Apo85

A. Apostolico. The myriad virtues of subword trees. In A. Apostolico and Z. Galil, editors, Combinatorial algorithms on words. Springer-Verlag, 1985.

APT79

B. Aspvall, M. Plass, and R. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Info. Proc. Letters, 8:121-123, 1979.

Aro96

S. Arora. Polynomial time approximations schemes for Euclidean TSP and other geometric problems. In Proc. 37th IEEE Foundations of Computer Science (FOCS '96), pages 1-10, 1996.

AS89

C. Aragon and R. Seidel. Randomized search trees. In Proc. 30th IEEE Symp. Foundations of Computer Science, pages 540-545, 1989.

Ata83

M. Atallah. A linear time algorithm for the Hausdorff distance between convex polygons. Info. Proc. Letters, 8:207-209, 1983.

Ata84

M. Atallah. Checking similarity of planar figures. Internat. J. Comput. Inform. Sci., 13:279-290, 1984.

Aur91

F. Aurenhammer. Voronoi diagrams: a survey of a fundamental data structure. ACM Computing Surveys, 23:345-405, 1991.

Baa88

S. Baase. Computer Algorithms. Addison-Wesley, Reading MA, second edition, 1988.

BCGR92

D. Berque, R. Cecchini, M. Goldberg, and R. Rivenburgh. The SetPlayer system for symbolic computation on power sets. J. Symbolic Computation, 14:645-662, 1992.

BCW90

T. Bell, J. Cleary, and I. Witten. Text Compression. Prentice Hall, Englewood Cliffs NJ, 1990.

BDH97

C. Barber, D. Dobkin, and H. Huhdanpaa. The Quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software, 22:469-483, 1997.

Bel58

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

Ben75

J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18:509-517, 1975.

Ben86

J. Bentley. Programming Pearls. Addison-Wesley, Reading MA, 1986.

Ben90

J. Bentley. More Programming Pearls. Addison-Wesley, Reading MA, 1990.

Ben92a

J. Bentley. Fast algorithms for geometric traveling salesman problems. ORSA J. Computing, 4:387-411, 1992.

Ben92b

J. L. Bentley. Software exploratorium: The trouble with qsort. UNIX Review, 10(2):85-93, February 1992.

Ber89

C. Berge. Hypergraphs. North-Holland, Amsterdam, 1989.

BETT94

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Algorithms for drawing graphs: An annotated bibliography. Computational Geometry: Theory and Applications, 4, 1994.

BFP 72

M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection. J. Computer and System Sciences, 7:448-461, 1972.

BG95

J. Berry and M. Goldberg. Path optimization and near-greedy analysis for graph partitioning: An empirical study. In Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pages 223-232, 1995.

BGL 95

C. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. In Proc. 11th ACM Symposium on Computational Geometry, pages 306-315, 1995.

BGS95

M Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs, and non-approximability - towards tight results. In Proc. IEEE 36th Symp. Foundations of Computer Science, pages 422-431, 1995.

BH90

F. Buckley and F. Harary. Distances in Graphs. Addison-Wesley, Redwood City, Calif., 1990.

BJ85

S. Bent and J. John. Finding the median requires 2n comparisons. In Proc. 17th ACM Symp. on Theory of Computing, pages 213-216, 1985.

BJL 91

A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yanakakis. Linear approximation of shortest superstrings. In Proc. 23rd ACM Symp. on Theory of Computing., pages 328-336, 1991.

BJLM83

J. Bentley, D. Johnson, F. Leighton, and C. McGeoch. An experimental study of bin packing. In Proc. 21st Allerton Conf. on Communication, Control, and Computing, pages 51-60, 1983.

BL77

B. P. Buckles and M. Lybanon. Generation of a vector from the lexicographical index. ACM Trans. Math. Softw., 3(2):180-182, June 1977.

BLS91

D. Bailey, K. Lee, and H. Simon. Using Strassen's algorithm to accelerate the solution of linear systems. J. Supercomputing, 4:357-371, 1991.

Blu67

H. Blum. A transformation for extracting new descriptions of shape. In W. Wathen-Dunn, editor, Models for the Perception of speech and Visual Form, pages 362-380. MIT Press, 1967.

BLW76

N. L. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.

BM53

G. Birkhoff and S. MacLane. A survey of modern algebra. Macmillian, New York, 1953.

BM72

R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.

BM77

R. Boyer and J. Moore. A fast string-searching algorithm. Communications of the ACM, 20:762-772, 1977.

BM89

J. Boreddy and R. N. Mukherjee. An algorithm to find polygon similarity. Inform. Process. Lett., 33(4):205-206, 1989.

BO79

J. Bentley and T. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28:643-647, 1979.

BO83

M. Ben-Or. Lower bounds for algebraic computation trees. In Proc. Fifteenth ACM Symp. on Theory of Computing, pages 80-86, 1983.

BP76

E. Balas and M. Padberg. Set partitioning - a survey. SIAM Review, 18:710-760, 1976.

BR80

I. Barrodale and F. D. K. Roberts. Solution of the constrained linear approximation problem. ACM Trans. Math. Softw., 6(2):231-235, June 1980.

BR95

A. Binstock and J. Rex. Practical Algorithms for Programmers. Addison-Wesley, Reading MA, 1995.

Bre73

R. Brent. Algorithms for minimization without derivatives. Prentice-Hall, Englewood Cliffs NJ, 1973.

Bre74

R. P. Brent. A Gaussian pseudo-random number generator. Commun. ACM, 17(12):704-706, December 1974.

Brè79

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

Bri74

E. Brigham. The Fast Fourier Transform. Prentice Hall, Englewood Cliffs NJ, 1974.

Bro74

F. Brooks. The Mythical Man-Month. Addison-Wesley, Reading MA, 1974.

Bro88

R. Brown. Calendar queuing method for future event list manipulation. Comm. ACM, 30, 1988.

Brz64

J. Brzozowski. Derivatives of regular expressions. J. ACM, 11:481-494, 1964.

BS76

J. Bentley and M. Shamos. Divide-and-conquer in higher-dimensional space. In Proc. Eighth ACM Symp. Theory of Computing, pages 220-230, 1976.

BS81

I. Barrodale and G. F. Stuart. A Fortran program for solving . ACM Trans. Math. Softw., 7(3):391-397, September 1981.

BS86

G. Berry and R. Sethi. From regular expressions to deterministic automata. Theoretical Computer Science, 48:117-126, 1986.

BS93

E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, Berlin, 1993.

BS96

E. Bach and J. Shallit. Algorithmic Number Theory: Efficient Algorithms, volume 1. MIT Press, Cambridge MA, 1996.

BS97

R. Bradley and S. Skiena. Fabricating arrays of strings. In Proc. First Int. Conf. Computational Molecular Biology (RECOMB '97), pages 57-66, 1997.

BT92

J. Buchanan and P. Turner. Numerical methods and analysis. McGraw-Hill, New York, 1992.

Buc94

A. G. Buckley. A Fortran 90 code for unconstrained nonlinear minimization. ACM Trans. Math. Softw., 20(3):354-372, September 1994.

BW91

G. Brightwell and P. Winkler. Counting linear extensions is #P-complete. In Proc. 23rd ACM Symp. Theory Computing (STOC), pages 175-181, 1991.

BYGNR94

R. Bar-Yehuda, D. Geiger, J. Naor, and R. Roth. Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference. In Proc. Fifth ACM-SIAM Symp. Discrete Algorithms, pages 344-354, 1994.

Can87

J. Canny. The complexity of robot motion planning. MIT Press, Cambridge MA, 1987.

CC92

S. Carlsson and J. Chen. The complexity of heaps. In Proc. Third ACM-SIAM Symp. on Discrete Algorithms, pages 393-402, 1992.

CCDG82

P. Chinn, J. Chvátolvá, A. K. Dewdney, and N. E. Gibbs. The bandwidth problem for graphs and matrices - a survey. J. Graph Theory, 6:223-254, 1982.

CD85

B. Chazelle and D. Dobkin. Optimal convex decompositions. In G. Toussaint, editor, Computational Geometry, pages 63-133. North-Holland, Amsterdam, 1985.

CDT95

G. Carpento, M. Dell'Amico, and P. Toth. CDT: A subroutine for the exact solution of large-scale, asymmetric traveling salesman problems. ACM Trans. Math. Softw., 21(4):410-415, December 1995.

CE92

B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments. J. ACM, 39:1-54, 1992.

CG94

B. Cherkassky and A. Goldberg. On implementing push-relabel method for the maximum flow problem. Technical Report 94-1523, Department of Computer Science, Stanford University, 1994.

CGJ96

E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: a survey. In D. Hochbaum, editor, Approximation algorithms. PWS Publishing, 1996.

CGL85

B. Chazelle, L. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25:76-90, 1985.

CGPS76

H. L. Crane Jr., N. F. Gibbs, W. G. Poole Jr., and P. K. Stockmeyer. Matrix bandwidth and profile reduction. ACM Trans. Math. Softw., 2(4):375-377, December 1976.

CGR93

B. Cherkassky, A. Goldberg, and T. Radzik. Shortest paths algorithms: theory and experimental evaluation. Technical Report 93-1480, Department of Computer Science, Stanford University, 1993.

Cha71

J. M. Chambers. Partial sorting. Commun. ACM, 14(5):357-358, May 1971.

Cha91

B. Chazelle. Triangulating a simple polygon in linear time. Discrete and Computational Geometry, 6:485-524, 1991.

Che80

T-Y. Cheung. A program for the multifacility location problem with rectilinear distance by the minimum-cut approach. ACM Trans. Math. Softw., 6(3):430-431, September 1980.

Chr76

N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh PA, 1976.

CHT90

J. Cai, X. Han, and R. Tarjan. New solutions to four planar graph problems. Technical report, New York University, 1990.

Chv83

V. Chvatal. Linear Programming. Freeman, San Francisco, 1983.

CK70

D. Chand and S. Kapur. An algorithm for convex polytopes. J. ACM, 17:78-86, 1970.

CK75

N. Christofides and S. Korman. A computational survey of methods for the set covering problem. Management Science, 21:591-599, 1975.

CK80

W. Cheney and D. Kincaid. Numerical Mathematics and Computing. Brooks/Cole, Monterey CA, 1980.

CK94

A. Chetverin and F. Kramer. Oligonucleotide arrays: New concepts and possibilities. Bio/Technology, 12:1093-1099, 1994.

Cla92

K. L. Clarkson. Safe and effective determinant evaluation. In Proc. 31st IEEE Symposium on Foundations of Computer Science, pages 387-395, Pittsburgh, PA, 1992.

CLR90

T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, Cambridge MA, 1990.

CM69

E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.

Cof76

E. Coffman. Computer and Job shop Scheduling. Wiley, New York, 1976.

Coh94

E. Cohen. Estimating the size of the transitive closure in linear time. In 35th Annual Symposium on Foundations of Computer Science, pages 190-200. IEEE, 1994.

Coo71

S. Cook. The complexity of theorem proving procedures. In Proc. Third ACM Symp. Theory of Computing, pages 151-158, 1971.

CP90

R. Carraghan and P. Paradalos. An exact algorithm for the maximum clique problem. In Operations Research Letters, volume 9, pages 375-382, 1990.

CR76

J. Cohen and M. Roth. On the implementation of Strassen's fast multiplication algorithm. Acta Informatica, 6:341-355, 1976.

CR94

M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.

Cra94

R. Crandall. Topics in Scientific Computation. Telos/Springer-Verlag, New York, 1994.

CS93

J. Conway and N. Sloane. Sphere packings, lattices, and groups. Springer-Verlag, New York, 1993.

CT65

J. Cooley and J. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19:297-301, 1965.

CT71

M. W. Coleman and M. S. Taylor. Circular integer partitioning. Commun. ACM, 14(1):48, January 1971.

CT80

G. Carpaneto and P. Toth. Solution of the assignment problem. ACM Trans. Math. Softw., 6(1):104-111, March 1980.

CT92

Y. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proc. IEEE, 80:1412-1434, 1992.

CW79

B. Commentz-Walter. A string matching algorithm fast on the average. In Proc. Sixth Int. Coll. on Automata, Languages, and Programming (ICALP), pages 118-132. Springer Verlag, Lecture Notes in Computer Science, 1979.

CW87

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. In Proc. Nineteenth ACM Symp. Theory of Computing, pages 1-6, 1987.

Dan63

G. Dantzig. Linear programming and extensions. Princeton University Press, Princeton NJ, 1963.

Dau92

I. Daubechies. Ten Lectures on Wavelets. SIAM, Philadelphia, 1992.

DB74

G. Dahlquist and A. Bjorck. Numerical Methods. Prentice-Hall, Englewood Cliffs NJ, 1974.

DB86

G. Davies and S. Bowsher. Algorithms for pattern matching. Software - Practice and Experience, 16:575-601, 1986.

Den82

D. Denning. Cryptography and Data Security. Addison-Wesley, Reading MA, 1982.

DF79

E. Denardo and B. Fox. Shortest-route methods: 1. reaching, pruning, and buckets. Operations Research, 27:161-186, 1979.

DFJ54

G. Dantzig, D. Fulkerson, and S. Johnson. Solution of a large-scale traveling-salesman problem. Operations Research, 2:393-410, 1954.

dFPP88

H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fary embeddings of planar graphs. In Proc. of the 20th Symposium on the Theory of Computing, pages 426-433. ACM, 1988.

DG87

J. Dongarra and E. Grosse. Distribution of mathematical software via electronic mail. Communications of the ACM, 30:403-407, 1987.

DGKK79

R. Dial, F. Glover, D. Karney, and D. Klingman. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks, 9:215-248, 1979.

DH73

R. Duda and P. Hart. Pattern Classification and Scene Analysis. Wiley-Interscience, New York, 1973.

DH92

D. Du and F. Hwang. A proof of Gilbert and Pollak's conjecture on the Steiner ratio. Algorithmica, 7:121-135, 1992.

Dij59

E. W. Dijkstra. A note on two problems in connection with graphs. Nuerische Mathematik, 1:269-271, 1959.

DJ92

G. Das and D. Joseph. Minimum vertex hulls for polyhedral domains. Theoret. Comput. Sci., 103:107-135, 1992.

DL76

D. Dobkin and R. Lipton. Multidimensional searching problems. SIAM J. Computing, 5:181-186, 1976.

DLR79

D. Dobkin, R. Lipton, and S. Reiss. Linear programming is log-space hard for P. Info. Processing Letters, 8:96-97, 1979.

DM80

D. Dobkin and J. I. Munro. Determining the mode. Theoretical Computer Science, 12:255-263, 1980.

DM97

K. Daniels and V. Milenkovic. Multiple translational containment. part I: an approximation algorithm. Algorithmica, 1997.

DMBS79

J. Dongarra, C. Moler, J. Bunch, and G. Stewart. LINPACK User's Guide. SIAM Publications, Philadelphia, 1979.

DNRT81

J. J. Ducroz, S. M. Nugent, J. K. Reid, and D. B. Taylor. Solution of real linear equations in a paged virtual store. ACM Trans. Math. Softw., 7(4):537-541, December 1981.

Dor94

S. Dorward. A survey of object-space hidden surface removal. Int. J. Computational Geometry Theory and Applications, 4:325-362, 1994.

DP73

D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Canadian Cartographer, 10(2):112-122, December 1973.

DP84

N. Deo and C. Pang. Shortest path algorithms: Taxonomy and annotation. Networks, 14:275-323, 1984.

DR90

N. Dershowitz and E. Reingold. Calendrical calculations. Software - Practice and Experience, 20:899-928, 1990.

DR97

N. Dershowitz and E. Reingold. Calendrical Calculations. Cambridge University Press, New York, 1997.

DRR 95

S. Dawson, C.R. Ramakrishnan, I.V. Ramakrishnan, K. Sagonas, S. Skiena, T. Swift, and D.S. Warren. Unification factoring for efficient execution of logic programs. In 22nd ACM Symposium on Principles of Programming Languages (POPL '95), pages 247-258, 1995.

DS88

D. Dobkin and D. Silver. Recipes for geometry and numerical analysis. In Proc. 4th ACM Symp. Computational Geometry, pages 93-105, 1988.

Duf81

S. Duff. Permutations for a zero-free diagonal. ACM Trans. Math. Softw., 7(3):387-390, September 1981.

dVS82

G. de V. Smit. A comparison of three string matching algorithms. Software - Practice and Experience, 12:57-66, 1982.

DZ95

D. Dor and U. Zwick. Selecting the median. In Proc. Sixth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 28-37, 1995.

Ebe88

J. Ebert. Computing Eulerian trails. Info. Proc. Letters, 28:93-97, 1988.

Edd77

W. F. Eddy. CONVEX: a new convex hull algorithm for planar sets. ACM Trans. Math. Softw., 3(4):411-412, December 1977.

Ede87

H. Edelsbrunner. Algorithms for Combinatorial Geometry. Springer-Verlag, Berlin, 1987.

Edm65

J. Edmonds. Paths, trees, and flowers. Canadian J. Math., 17:449-467, 1965.

Edm71

J. Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1:126-136, 1971.

EG60

P. Erdös and T. Gallai. Graphs with prescribed degrees of vertices. Mat. Lapok (Hungarian), 11:264-274, 1960.

EG89

H. Edelsbrunner and L. Guibas. Topologically sweeping an arrangement. J. Computer and System Sciences, 38:165-194, 1989.

EG91

H. Edelsbrunner and L. Guibas. Corrigendum: Topologically sweeping an arrangement. J. Computer and System Sciences, 42:249-251, 1991.

EGIN92

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification: A technique for speeding up dynamic graph algorithms. In Proc. 33rd IEEE Symp. on Foundations of Computer Science (FOCS), pages 60-69, 1992.

EGS86

H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Computing, 15:317-340, 1986.

EJ73

J. Edmonds and E. Johnson. Matching, Euler tours, and the Chinese postman. Math. Programming, 5:88-124, 1973.

EKA84

M. I. Edahiro, I. Kokubo, and T. Asano. A new point location algorithm and its practical efficiency - comparison with existing algorithms. ACM Trans. Graphics, 3:86-109, 1984.

EKS83

H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. on Information Theory, IT-29:551-559, 1983.

ELS93

P. Eades, X. Lin, and W. F. Smyth. A fast and effective heuristic for the feedback arc set problem. Info. Proc. Letters, 47:319-323, 1993.

EM94

H. Edelsbrunner and Ernst P. Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13:43-72, 1994.

ES74

P. Erdös and J. Spencer. Probabilistic Methods in Combinatorics. Academic Press, New York, 1974.

ES86

H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete and Computational Geometry, 1:25-44, 1986.

ESS93

H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements. SIAM J. Computing, 22:418-429, 1993.

ESV96

F. Evans, S. Skiena, and A. Varshney. Optimizing triangle strips for fast rendering. In Proc. IEEE Visualization '96, pages 319-326, 1996.

Eul36

L. Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae, 8:128-140, 1736.

Eve79a

S. Even. Graph Algorithms. Computer Science Press, Rockville MD, 1979.

Eve79b

G. Everstine. A comparison of three resequencing algorithms for the reduction of matrix profile and wave-front. Int. J. Numerical Methods in Engr., 14:837-863, 1979.

F48

I. Fáry. On straight line representation of planar graphs. Acta. Sci. Math. Szeged, 11:229-233, 1948.

Faj87

S. Fajtlowicz. On conjectures of Graffiti. Discrete Mathematics, 72:113-118, 1987.

FF62

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

Fis95

P. Fishwick. Simulation Model Design and Execution: Building Digital Worlds. Prentice Hall, Englewood Cliffs, NJ, 1995.

FJ95

A. Frieze and M. Jerrum. An analysis of a Monte Carlo algorithm for estimating the permanent. Combinatorica, 15, 1995.

Fle74

H. Fleischner. The square of every two-connected graph is Hamiltonian. J. Combinatorial Theory, B, 16:29-34, 1974.

Fle80

R. Fletcher. Practical Methods of Optimization: Unconstrained Optimization, volume 1. John Wiley, Chichester, 1980.

Flo62

R. Floyd. Algorithm 97 (shortest path). Communications of the ACM, 7:345, 1962.

Flo64

R. Floyd. Algorithm 245 (treesort). Communications of the ACM, 18:701, 1964.

FM71

M. Fischer and A. Meyer. Boolean matrix multiplication and transitive closure. In IEEE 12th Symp. on Switching and Automata Theory, pages 129-131, 1971.

For87

S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.

For92

S. Fortune. Voronoi diagrams and Delaunay triangulations. In D.-Z. Du and F. Hwang, editors, Computing in Euclidean Geometry, volume 1, pages 193-234. World Scientific, 1992.

FP75a

D. Fayard and G. Plateau. Resolution of the 0-1 knapsack problem: Comparison of methods. Math. Programming, 8:272-307, 1975.

FP75b

H. Feng and T. Pavlidis. Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition. IEEE Transactions on Computers, C-24:636-650, 1975.

FR75

R. Floyd and R. Rivest. Expected time bounds for selection. Communications of the ACM, 18:165-172, 1975.

FR94

M. Fürer and B. Raghavachari. Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms, 17:409-423, 1994.

Fra79

D. Fraser. An optimized mass storage FFT. ACM Trans. Math. Softw., 5(4):500-517, December 1979.

Fre62

E. Fredkin. Trie memory. Communications of the ACM, 3:490-499, 1962.

FT87

M. Fredman and R. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596-615, 1987.

Fuj96

T. Fujito. A note on approximation of the vertex cover and feedback vertex set problems. Info. Proc. Letters, 59:59-63, 1996.

FvW93

S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. In Proc. 9th ACM Symp. Computational Geometry, pages 163-172, 1993.

FW77

S. Fiorini and R. Wilson. Edge-colourings of graphs. Research Notes in Mathematics 16, Pitman, London, 1977.

FW93

M. Fredman and D. Willard. Surpassing the information theoretic bound with fusion trees. J. Computer and System Sci., 47:424-436, 1993.

Gab76

H. Gabow. An efficient implementation of Edmond's algorithm for maximum 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.

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 Structures. Addison-Wesley, Wokingham, England, second edition, 1991.

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.

GHMS93

L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink. Approximating 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.

GI89

D. Gusfield and R. Irving. The Stable Marriage Problem: structure and algorithms. 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.

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.

GJPT78

M. Garey, D. Johnson, F. Preparata, and R. Tarjan. Triangulating a simple polygon. Info. Proc. Letters, 7:175-180, 1978.

GK79

A. Goralcikiova and V. Konbek. A reduct and closure algorithm for graphs. In Mathematical Foundations of Computer Science, pages 301-307. Springer Verlag, Lecture Notes in Computer Science V. 74, 1979.

GK93

A. Goldberg and R. Kennedy. An efficient cost scaling algorithm for the assignment problem. Technical Report 93-1481, Department of Computer Science, Stanford University, 1993.

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.

Glo89a

F. Glover. Tabu search - Part 1. ORSA Journal on Computing, 1(3):190-206, 1989.

Glo89b

F. Glover. Tabu search - Part 2. ORSA Journal on Computing, 2(1):4-32, 1989.

Glo90

F. Glover. Tabu search: A tutorial. Interfaces, Vol. 20, :4, 74-94, 1990.

GM86

G. Gonnet and J.I. Munro. Heaps on heaps. SIAM J. Computing, 15:964-971, 1986.

Gol89

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.

Gol92

A. Goldberg. An efficient implementation of a scaling minimum-cost flow algorithm. Technical Report 92-1439, Department of Computer Science, Stanford University, 1992.

Gol93

L. Goldberg. Efficient Algorithms for Listing Combinatorial Structures. Cambridge University Press, 1993.

GP68

E. Gilbert and H. Pollak. Steiner minimal trees. SIAM J. Applied Math., 16:1-29, 1968.

GP79

B. Gates and C. Papadimitriou. Bounds for sorting by prefix reversals. Discrete Mathematics, 27:47-57, 1979.

GPS76

N. Gibbs, W. Poole, and P. Stockmeyer. A comparison of several bandwidth and profile reduction algorithms. ACM Trans. Math. Software, 2:322-330, 1976.

Gra53

F. Gray. Pulse code communication. US Patent 2632058, March 17, 1953.

Gra72

R. Graham. An efficient algorithm for determining the convex hull of a finite planar point set. Info. Proc. Letters, 1:132-133, 1972.

GS62

D. Gale and L. Shapely. College admissions and the stability of marriages. American Math. Monthly, 69:9-14, 1962.

GS78

L. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th IEEE Symp. Foundations of Computer Science, pages 8-21, 1978.

GT88

A. Goldberg and R. Tarjan. A new approach to the maximum flow problem. J. ACM, pages 921-940, 1988.

GT89

H. Gabow and R. Tarjan. Faster scaling algorithms for network problems. SIAM J. Computing, 18:1013-1036, 1989.

Gup66

R. P. Gupta. The chromatic index and the degree of a graph. Notices of the Amer. Math. Soc., 13:66T-429, 1966.

Gus97

D. Gusfield. String Algorithms. Cambridge University Press, 1997.

GW95

M. Goemans and D. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. J. ACM, 42:1115-1145, 1995.

HD80

P. Hall and G. Dowling. Approximate string matching. ACM Computing Surveys, 12:381-402, 1980.

HG95

P. Heckbert and M. Garland. Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS-95-181, School of Computer Science, Carnegie-Mellon University, 1995.

Him94

M. Himsolt. GraphEd: A graphical platform for the implementation of graph algorithms. In Proc. Graph Drawing (GD '94), volume 894, pages 182-193, 1994.

Hir75

D. Hirschberg. A linear-space algorithm for computing maximum common subsequences. Communications of the ACM, 18:341-343, 1975.

HJS84

R. E. Haymond, J. P. Jarvis, and D. R. Shier. Minimum spanning tree for moderate integer weights. ACM Trans. Math. Softw., 10(1):108-111, March 1984.

HK73

J. Hopcroft and R. Karp. An algorithm for maximum matchings in bipartite graphs. SIAM J. Computing, 2:225-231, 1973.

HK90

D. P. Huttenlocher and K. Kedem. Computing the minimum Hausdorff distance for point sets under translation. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 340-349, 1990.

HM83

S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conf. Found. Comput. Theory, pages 207-218. Lecture Notes in Computer Science, Vol. 158, 1983.

HMMN84

S. Hertel, K. Mehlhorn, M. Mäntylä, and J. Nievergelt. Space sweep solves intersection of two convex polyhedra elegantly. Acta Informatica, 21:501-519, 1984.

Hoa61

C. A. R. Hoare. Algorithm 63 (partition) and algorithm 65 (find). Communications of the ACM, 4:321-322, 1961.

Hoa62

C. A. R. Hoare. Quicksort. Computer Journal, 5:10-15, 1962.

Hoc96

D. Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing, Boston, 1996.

Hof82

C. M. Hoffmann. Group-theoretic algorithms and graph isomorphism, volume 136 of Lecture Notes in Computer Science. Springer-Verlag Inc., New York, 1982.

Hof89

C. Hoffman. The problem of accuracy and robustness in geometric computation. Computer, 22:31-42, 1989.

Hol75

J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.

Hol81

I. Holyer. The NP-completeness of edge colorings. SIAM J. Computing, 10:718-720, 1981.

Hol92

J. H. Holland. Genetic algorithms. Scientific American, 267(1):66-72, July 1992.

Hop71

J. Hopcroft. An algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The theory of machines and computations, pages 189-196. Academic Press, New York, 1971.

Hor80

R. N. Horspool. Practical fast searching in strings. Software - Practice and Experience, 10:501-506, 1980.

HP73

F. Harary and E. Palmer. Graphical enumeration. Academic Press, New York, 1973.

HRW92

R. Hwang, D. Richards, and P. Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. North Holland, Amsterdam, 1992.

HS77

J. Hunt and T. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20:350-353, 1977.

HS94

J. Hershberger and J. Snoeyink. An implementation of the Douglas-Peucker algorithm for line simplification. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 383-384, 1994.

HSS87

J. Hopcroft, J. Schwartz, and M. Sharir. Planning, geometry, and complexity of robot motion. Ablex Publishing, Norwood NJ, 1987.

HT73a

J. Hopcroft and R. Tarjan. Dividing a graph into triconnected components. SIAM J. Computing, 2:135-158, 1973.

HT73b

J. Hopcroft and R. Tarjan. Efficient algorithms for graph manipulation. Communications of the ACM, 16:372-378, 1973.

HT74

J. Hopcroft and R. Tarjan. Efficient planarity testing. J. ACM, 21:549-568, 1974.

HT84

D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13:338-355, 1984.

Hua92

X. Huang. A contig assembly program based on sensitive detection of fragment overlaps. Genomics, 1992.

Hua94

X. Huang. On global sequence alignment. CABIOS, 10:227-235, 1994.

Huf52

D. Huffman. A method for the construction of minimum-redundancy codes. Proc. of the IRE, 40:1098-1101, 1952.

HW74

J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs. In Proc. Sixth Annual ACM Symposium on Theory of Computing, pages 172-184, 1974.

HWK94

T. He, S. Wang, and A. Kaufman. Wavelet-based volume morphing. In Proc. IEEE Visualization '94, pages 85-92, 1994.

HWL87

Jr. H. W. Lenstra. Factoring integers with elliptic curves. Annals of Mathematics, 126:649-673, 1987.

IK75

O. Ibarra and C. Kim. Fast approximation algorithms for knapsack and sum of subset problems. J. ACM, 22:463-468, 1975.

Ita78

A. Itai. Two commodity flow. J. ACM, 25:596-611, 1978.

JAMS91

D. Johnson, C. Aragon, C. McGeoch, and D. Schevon. Optimization by simulated annealing: an experimental evaluation; partII, graph coloring and number partitioning. In Operations Research, volume 39, pages 378-406, 1991.

Jan76

W. Janko. A list insertion sort for keys with arbitrary key distribution. ACM Trans. Math. Softw., 2(2):204-206, June 1976.

Jar73

R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Info. Proc. Letters, 2:18-21, 1973.

JD88

A. Jain and R. Dubes. Algorithms for Clustering Data. Prentice-Hall, Englewood Cliffs NJ, 1988.

JM93

D. Johnson and C. McGeoch, editors. Network Flows and Matching: First DIMACS Implementation Challenge, volume 12. American Mathematics Society, Providence RI, 1993.

Joh63

S. M. Johnson. Generation of permutations by adjacent transpositions. Math. Computation, 17:282-285, 1963.

Joh74

D. Johnson. Approximation algorithms for combinatorial problems. J. Computer and System Sciences, 9:256-278, 1974.

Joh90

D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 67-162. MIT Press, 1990.

Jon86

D. W. Jones. An empirical comparison of priority-queue and event-set implementations. Communications of the ACM, 29:300-311, 1986.

Kah67

D. Kahn. The Code breakers: the story of secret writing. Macmillan, New York, 1967.

Kah80

D. A. Kahamer. Fortran implementation of heap programs for efficient table maintenance. ACM Trans. Math. Softw., 6(3):444-449, September 1980.

Kar72

R. M. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.

Kar84

N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373-395, 1984.

Kar96a

D. Karger. Minimum cuts in near-linear time. In Proc. 28th ACM Symp. Theory of Computing, pages 56-63, 1996.

Kar96b

H. Karloff. How good is the Goemans-Williamson MAX CUT algorithm? In Proc. Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 427-434, 1996.

Kei85

M. Keil. Decomposing a polygon into simpler components. SIAM J. Computing, 14:799-817, 1985.

KGV83

S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.

KH80

J. Kennington and R. Helgason. Algorithms for Network Programming. Wiley-Interscience, New York, 1980.

Kha79

L. Khachian. A polynomial algorithm in linear programming. Soviet Math. Dokl., 20:191-194, 1979.

Kir79

D. Kirkpatrick. Efficient computation of continuous skeletons. In Proc. 20th IEEE Symp. Foundations of Computing, pages 28-35, 1979.

Kir83

D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Computing, 12:28-35, 1983.

KKT95

D. Karger, P. Klein, and R. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42:321-328, 1995.

KL70

B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291-307, 1970.

KM72

V. Klee and G. Minty. How good is the simplex algorithm. In Inequalities III, pages 159-172, New York, 1972. Academic Press.

KM95

J. D. Kececioglu and E. W. Myers. Combinatorial algorithms for DNA sequence assembly. Algorithmica, 13(1/2):7-51, January 1995.

KMP77

D. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J. Computing, 6:323-350, 1977.

Kno79

H. D. Knoble. An efficient one-way enciphering algorithm. ACM Trans. Math. Softw., 5(1):108-111, March 1979.

Knu73a

D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, Reading MA, second edition, 1973.

Knu73b

D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Reading MA, 1973.

Knu81

D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading MA, second edition, 1981.

Knu94

D. Knuth. The Stanford GraphBase: a platform for combinatorial computing. ACM Press, New York, 1994.

KO63

A. Karatsuba and Yu. Ofman. Multiplication of multi-digit numbers on automata. Sov. Phys. Dokl., 7:595-596, 1963.

KOS91

A. Kaul, M. A. O'Connor, and V. Srinivasan. Computing Minkowski sums of regular polygons. In Proc. 3rd Canad. Conf. Comput. Geom., pages 74-77, 1991.

Koz92

J. R. Koza. Genetic Programming. MIT Press, Cambridge, MA, 1992.

KPS89

B. Korte, H. Prömel, and A. Steger. Steiner trees in VLSI-layout. In B. Korte, L. Lovasz, H. Prömel, and A. Schrijver, editors, Paths, Flows, and VLSI-layout, pages 185-214. Springer-Verlag, Berlin, 1989.

KR87

R. Karp and M. Rabin. Efficient randomized pattern-matching algorithms. IBM J. Research and Development, 31:249-260, 1987.

KR91

A. Kanevsky and V. Ramachandran. Improved algorithms for graph four-connectivity. J. Comp. Sys. Sci., 42:288-306, 1991.

Kru56

J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7:48-50, 1956.

KS85

M. Keil and J. R. Sack. Computational Geometry, chapter Minimum decomposition of geometric objects, pages 197-216. North-Holland, 1985.

KS86

D. Kirkpatrick and R. Siedel. The ultimate planar convex hull algorithm? SIAM J. Computing, 15:287-299, 1986.

KS90

K. Kedem and M. Sharir. An efficient motion planning algorithm for a convex rigid polygonal object in 2-dimensional polygonal space. Discrete and Computational Geometry, 5:43-75, 1990.

Kuh75

H. W. Kuhn. Steiner's problem revisited. In G. Dantzig and B. Eaves, editors, Studies in Optimization, pages 53-70. Mathematical Association of America, 1975.

Kur30

K. Kuratowski. Sur le problème des courbes gauches en topologie. Fund. Math., 15:217-283, 1930.

Kwa62

M. Kwan. Graphic programming using odd and even points. Chinese Math., 1:273-277, 1962.

Lat91

J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.

Law76

E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, Fort Worth TX, 1976.

Lee82

D. T. Lee. Medial axis transformation of a planar shape. IEEE Trans. Pattern Analysis and Machine Intelligence, PAMI-4:363-369, 1982.

Lee94

H. Leeb. pLab - a system for testing random numbers. In Proc. Int. Workshop Parallel Numerics, pages 89-99. Slovak Academy of Science, Institute for Informatics, Slovakia, 1994. Also available via ftp from http://random.mat.sbg.ac.at/ftp/pub/publications/leeb/smolenice/.

Len87

T. Lengauer. Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs. J. Algorithms, 8, 1987.

Len89

T. Lengauer. Hierarchical planarity testing algorithms. J. ACM, 36(3):474-509, July 1989.

Len90

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester, England, 1990.

Lev92

J. L. Leva. A normal random number generator. ACM Trans. Math. Softw., 18(4):454-455, December 1992.

Lew82

J. G. Lewis. The Gibbs-Poole-Stockmeyer and Gibbs-King algorithms for reordering sparse matrices. ACM Trans. Math. Softw., 8(2):190-194, June 1982.

Lin65

S. Lin. Computer solutions of the traveling salesman problem. Bell System Tech. J., 44:2245-2269, 1965.

LK73

S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21:498-516, 1973.

LLK83

J. K. Lenstra, E. L. Lawler, and A. Rinnooy Kan. Theory of Sequencing and Scheduling. Wiley, New York, 1983.

LLKS85

E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Shmoys. The Traveling Salesman Problem. John Wiley, 1985.

LLS92

L. Lam, S.-W. Lee, and C. Suen. Thinning methodologies - a comprehensive survey. IEEE Trans. Pattern Analysis and Machine Intelligence, 14:869-885, 1992.

LP86

L. Lovász and M. Plummer. Matching Theory. North-Holland, Amsterdam, 1986.

LPW79

T. Lozano-Perez and M. Wesley. An algorithm for planning collision-free paths among polygonal obstacles. Comm. ACM, 22:560-570, 1979.

LR93

K. Lang and S. Rao. Finding near-optimal cuts: An empirical evaluation. In Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '93), pages 212-221, 1993.

LS87

V. Lumelski and A. Stepanov. Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, 3:403-430, 1987.

LS95

Y.-L. Lin and S. Skiena. Algorithms for square roots of graphs. SIAM J. Discrete Mathematics, 8:99-118, 1995.

LT79

R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36:346-358, 1979.

LT80

R. Lipton and R. Tarjan. Applications of a planar separator theorem. SIAM J. Computing, 9:615-626, 1980.

Luc91

E. Lucas. Récréations Mathématiques. Gauthier-Villares, Paris, 1891.

Luk80

E. M. Luks. Isomorphism of bounded valence can be tested in polynomial time. In Proc. of the 21st Annual Symposium on Foundations of Computing, pages 42-49. IEEE, 1980.

LV93

M. Li and P. Vitáni. An introduction to Kolmogorov complexity and its applications. Springer-Verlag, New York, 1993.

LW77

D. T. Lee and C. K. Wong. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica, 9:23-29, 1977.

LW88

T. Lengauer and E. Wanke. Efficient solution of connectivity problems on hierarchically defined graphs. SIAM J. Computing, 17:1063-1080, 1988.

LY93

C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proc. 25th ACM Symp. Theory of Computing (STOC), pages 286-293, 1993.

Man89

U. Manber. Introduction to Algorithms. Addison-Wesley, Reading MA, 1989.

Mar83

S. Martello. An enumerative algorithm for finding Hamiltonian circuits in a directed graph. ACM Trans. Math. Softw., 9(1):131-138, March 1983.

Mat87

D. W. Matula. Determining edge connectivity in O(nm). In 28th Ann. Symp. Foundations of Computer Science, pages 249-251. IEEE, 1987.

McC76

E. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23:262-272, 1976.

McH90

J. McHugh. Algorithmic Graph Theory. Prentice-Hall, Englewood Cliffs NJ, 1990.

McN83

J. M. McNamee. A sparse matrix package - part II: Special cases. ACM Trans. Math. Softw., 9(3):344-345, September 1983.

Meg83

N. Megiddo. Linear time algorithm for linear programming in and related problems. SIAM J. Computing, 12:759-776, 1983.

Meh84

K. Mehlhorn. Data structures and algorithms, volume 1-3. Springer-Verlag, Berlin, 1984.

Men27

K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:96-115, 1927.

MGH81

J. J. Moré, B. S. Garbow, and K. E. Hillstrom. Fortran subroutines for testing unconstrained optimization software. ACM Trans. Math. Softw., 7(1):136-140, March 1981.

MH78

R. Merkle and M Hellman. Hiding and signatures in trapdoor knapsacks. IEEE Trans. Information Theory, 24:525-530, 1978.

Mic92

Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin, 1992.

Mie58

W. Miehle. Link-minimization in networks. Operations Research, 6:232-243, 1958.

Mil76

G. Miller. Reimann's hypothesis and tests for primality. J. Computer and System Sciences, 13:300-317, 1976.

Mil89

V. Milenkovic. Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In Proc. 30th IEEE Symp. Foundations of Computer Science (FOCS), pages 500-505, 1989.

Mil97

V. Milenkovic. Multiple translational containment. part II: exact algorithms. Algorithmica, 1997.

Min78

H. Minc. Permanents, volume 6 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading MA, 1978.

Mit96

J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: Part II - A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems. University at Stony Brook, Part I appears in SODA'96, pp. 402-408, 1996.

MM90

U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. In Proceedings First ACM-SIAM Symposium on Discrete Algorithms, pages 319-327. SIAM, 1990.

MMI72

D. Matula, G. Marble, and J. Isaacson. Graph coloring algorithms. In R. C. Read, editor, Graph Theory and Computing, pages 109-122. Academic Press, 1972.

MN95

K. Mehlhorn and S. Näher. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96-102, 1995.

MO63

L. E. Moses and R. V. Oakford. Tables of Random Permutations. Stanford University Press, Stanford, Calif., 1963.

Moo59

E. F. Moore. The shortest path in a maze. In Proc. International Symp. Switching Theory, pages 285-292. Harvard University Press, 1959.

MP78

D. Muller and F. Preparata. Finding the intersection of two convex polyhedra. Theoretical Computer Science, 7:217-236, 1978.

MP80

W. Masek and M. Paterson. A faster algorithm for computing string edit distances. J. Computer and System Sciences, 20:18-31, 1980.

MR95

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, 1995.

MRRT53

N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, and A. H. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6):1087-1092, June 1953.

MS91

B. Moret and H. Shapiro. Algorithm from P to NP: Design and Efficiency. Benjamin/Cummings, Redwood City, CA, 1991.

MS93

M. Murphy and S. Skiena. Ranger: A tool for nearest neighbor search in high dimensions. In Proc. Ninth ACM Symposium on Computational Geometry, pages 403-404, 1993.

MS95a

D. Margaritis and S. Skiena. Reconstructing strings from substrings in rounds. Proc. 36th IEEE Symp. Foundations of Computer Science (FOCS), 1995.

MS95b

J. S. B. Mitchell and S. Suri. Separation and approximation of polyhedral objects. Comput. Geom. Theory Appl., 5:95-114, 1995.

MT85

S. Martello and P. Toth. A program for the 0-1 multiple knapsack problem. ACM Trans. Math. Softw., 11(2):135-140, June 1985.

MT87

S. Martello and P. Toth. Algorithms for knapsack problems. In S. Martello, editor, Surveys in Combinatorial Optimization, volume 31 of Annals of Discrete Mathematics, pages 213-258. North-Holland, 1987.

MT90a

S. Martello and P. Toth. Knapsack problems: algorithms and computer implementations. Wiley, New York, 1990.

MT90b

K. Mehlhorn and A. Tsakalidis. Data structures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 301-341. MIT Press, 1990.

Mul94

K. Mulmuley. Computational Geometry: an introduction through randomized algorithms. Prentice-Hall, New York, 1994.

MV80

S. Micali and V. Vazirani. An O algorithm for finding maximum matchings in general graphs. In Proc. 21st. Symp. Foundations of Computing, pages 17-27, 1980.

MW93

J. More and S. Wright. Optimization Software Guide. SIAM, Philadelphia PA, 1993.

Mye86

E. Myers. An O(n d) difference algorithm and its variations. Algorithmica, 1:514-534, 1986.

NC88

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. North-Holland, Amsterdam, 1988.

NH93

J. Nievergelt and K. Hinrichs. Algorithms and Data Structures with applications to graphics and geometry. Prentice Hall, Englewood Cliffs NJ, 1993.

NU95

Stefan Näher and C. Uhrig. The LEDA user manual, version r3.2. Available by ftp from ftp.mpi-sb.mpg.de in directory /pub/LEDA, 1995.

NW78

A. Nijenhuis and H. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, Orlando FL, second edition, 1978.

NW86

J. C. Nash and R. L. C. Wang. Subroutines for testing programs that compute the generalized inverse of a matrix. ACM Trans. Math. Softw., 12(3):274-277, September 1986.

NZ80

I. Niven and H. Zuckerman. An Introduction to the Theory of Numbers. Wiley, New York, fourth edition, 1980.

Ogn93

R. Ogniewicz. Discrete Voronoi Skeletons. Hartung-Gorre Verlag, Konstanz, Germany, 1993.

O'R87

J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, Oxford, 1987.

O'R94

J. O'Rourke. Computational Geometry in C. Cambridge University Press, New York, 1994.

Ort88

J. Ortega. Introduction to Parallel and Vector Solution of Linear Systems. Plenum, New York, 1988.

OvL81

M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Computer and System Sciences, 23:166-204, 1981.

OW85

J. O'Rourke and R. Washington. Curve similarity via signatures. In G. T. Toussaint, editor, Computational Geometry, pages 295-317. North-Holland, Amsterdam, Netherlands, 1985.

Pag74

R. L. Page. A minimal spanning tree clustering method. Commun. ACM, 17(6):321-323, June 1974.

Pal85

E. M. Palmer. Graphical Evolution: An Introduction to the Theory of Random Graphs. Wiley-Interscience, New York, 1985.

Pap76a

C. Papadimitriou. The complexity of edge traversing. J. ACM, 23:544-554, 1976.

Pap76b

C. Papadimitriou. The NP-completeness of the bandwidth minimization problem. Computing, 16:263-270, 1976.

Pap80

U. Pape. Shortest path lengths. ACM Trans. Math. Softw., 6(3):450-455, September 1980.

Par90

G. Parker. A better phonetic search. C Gazette, 5-4, June/July 1990.

Pav82

T. Pavlidis. Algorithms for Graphics and Image Processing. Computer Science Press, Rockville MD, 1982.

PFTV86

W. Press, B. Flannery, S. Teukolsky, and W. T. Vetterling. Numerical Recipes: the art of scientific computing. Cambridge University Press, 1986.

PGD82

D. Phillips and A. Garcia-Diaz. Fundamentals of Network Analysis. Prentice-Hall, Englewood Cliffs NJ, 1982.

PH80

M. Padberg and S. Hong. On the symmetric traveling salesman problem: a computational study. Math. Programming Studies, 12:78-107, 1980.

PL94

P. A. Pevzner and R. J. Lipshutz. Towards DNA sequencing chips. In 19th Int. Conf. Mathematical Foundations of Computer Science, volume 841, pages 143-158, Lecture Notes in Computer Science, 1994.

PM88

S. Park and K. Miller. Random number generators: Good ones are hard to find. Communications of the ACM, 31:1192-1201, 1988.

Pol57

G. Polya. How to Solve it. Princeton University Press, Princeton NJ, second edition, 1957.

Pom84

C. Pomerance. The quadratic sieve factoring algorithm. In T. Beth, N. Cot, and I. Ingemarrson, editors, Advances in Cryptology, volume 209, pages 169-182. Lecture Notes in Computer Science, Springer-Verlag, 1984.

PR79

S. Peleg and A. Rosenfield. Breaking substitution ciphers using a relaxation algorithm. Comm. ACM, 22:598-605, 1979.

Pra75

V. Pratt. Every prime has a succinct certificate. SIAM J. Computing, 4:214-220, 1975.

Pri57

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

Prü18

H. Prüfer. Neuer beweis eines satzes über permutationen. Arch. Math. Phys., 27:742-744, 1918.

PS82

C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982.

PS85

F. Preparata and M. Shamos. Computational Geometry. Springer-Verlag, New York, 1985.

PSW92

T. Pavlides, J. Swartz, and Y. Wang. Information encoding with two-dimensional bar-codes. IEEE Computer, 25:18-28, 1992.

Pug90

W. Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33:668-676, 1990.

PW83

S. Pizer and V. Wallace. To compute numerically: concepts and strategies. Little, Brown, Boston, 1983.

Rab80

M. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12:128-138, 1980.

Rab95

F. M. Rabinowitz. A stochastic algorithm for global optimization with constraints. ACM Trans. Math. Softw., 21(2):194-213, June 1995.

Raw92

G. Rawlins. Compared to What? Computer Science Press, New York, 1992.

RC55

Rand-Corporation. A million random digits with 100,000 normal deviates. The Free Press, Glencoe, IL, 1955.

RDC93

E. Reingold, N. Dershowitz, and S. Clamen. Calendrical calculations II: Three historical calendars. Software - Practice and Experience, 22:383-404, 1993.

Rei72

E. Reingold. On the optimality of some set algorithms. J. ACM, 19:649-659, 1972.

Rei91

G. Reinelt. TSPLIB - a traveling salesman problem library. ORSA J. Computing, 3:376-384, 1991.

Rei94

G. Reinelt. The traveling salesman problem: Computational solutions for TSP applications. In Lecture Notes in Computer Science 840, pages 172-186. Springer-Verlag, Berlin, 1994.

Ren84

R. J. Renka. Triangulation and interpolation at arbitrarily distributed points in the plane. ACM Trans. Math. Softw., 10(4):440-442, December 1984.

RHS89

A. Robison, B. Hafner, and S. Skiena. Eight pieces cannot cover a chessboard. Computer Journal, 32:567-570, 1989.

Riv77

R. Rivest. On the worst-case behavior of string-searching algorithms. SIAM J. Computing, 6:669-674, 1977.

Riv92

R. Rivest. The MD5 message digest algorithm. RFC 1321, 1992.

RND77

E. Reingold, J. Nievergelt, and N. Deo. Combinatorial algorithms: theory and practice. Prentice-Hall, Englewood Cliffs NJ, 1977.

RS96

H. Rau and S. Skiena. Dialing for documents: an experiment in information theory. Journal of Visual Languages and Computing, pages 79-95, 1996.

RSA78

R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21:120-126, 1978.

RSL77

D. Rosenkrantz, R. Stearns, and P. M. Lewis. An analysis of several heuristics for the traveling salesman problem. SIAM J. Computing, 6:563-581, 1977.

RSST96

N. Robertson, D. Sanders, P. Seymour, and R. Thomas. Efficiently four-coloring planar graphs. In Proc. 28th ACM Symp. Theory of Computing, pages 571-575, 1996.

RT81

E. Reingold and J. Tilford. Tidier drawings of trees. IEEE Trans. Software Engineering, 7:223-228, 1981.

Rus97

F. Ruskey. Combinatorial generation. book in preparation, 1997.

Ryt85

W. Rytter. Fast recognition of pushdown automaton and context-free languages. Information and Control, 67:12-22, 1985.

SA95

M. Sharir and P. Agarwal. Davenport-Schinzel sequences and their geometric applications. Cambridge University Press, New York, 1995.

Sam90a

H. Samet. Applications of spatial data structures. Addison-Wesley, Reading MA, 1990.

Sam90b

H. Samet. The design and analysis of spatial data structures. Addison-Wesley, Reading MA, 1990.

Sax80

J. B. Saxe. Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic and Discrete Methods, 1:363-369, 1980.

Sch94

B. Schneier. Applied Cryptography. Wiley, New York, 1994.

SD75

M. Syslo and J. Dzikiewicz. Computational experiences with some transitive closure algorithms. Computing, 15:33-39, 1975.

SD76

D. C. Schmidt and L. E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. J. ACM, 23:433-445, 1976.

SDK83

M. Syslo, N. Deo, and J. Kowalik. Discrete Optimization Algorithms with Pascal Programs. Prentice Hall, Englewood Cliffs NJ, 1983.

Sed77

R. Sedgewick. Permutation generation methods. Computing Surveys, 9:137-164, 1977.

Sed78

R. Sedgewick. Implementing quicksort programs. Communications of the ACM, 21:847-857, 1978.

Sed92

R. Sedgewick. Algorithms in C++. Addison-Wesley, Reading MA, 1992.

SF92

T. Schlick and A. Fogelson. TNPACK - a truncated Newton minimization package for large-scale problems: I. algorithm and usage. ACM Trans. Math. Softw., 18(1):46-70, March 1992.

SFG82

M. Shore, L. Foulds, and P. Gibbons. An algorithms for the Steiner problem in graphs. Networks, 12:323-333, 1982.

SH75

M. Shamos and D. Hoey. Closest point problems. In Proc. Sixteenth IEEE Symp. Foundations of Computer Science, pages 151-162, 1975.

SH76

M. Shamos and D. Hoey. Geometric intersection problems. In Proc. 17th IEEE Symp. Foundations of Computer Science, pages 208-215, 1976.

Sha78

M. Shamos. Computational Geometry. PhD thesis, Yale University, UMI #7819047, 1978.

Sha87

M. Sharir. Efficient algorithms for planning purely translational collision-free motion in two and three dimensions. In Proc. IEEE Internat. Conf. Robot. Autom., pages 1326-1331, 1987.

Sha93

R. Sharda. Linear and Discrete Optimization and Modeling Software: A Resource Handbook. Lionheart Publishing Inc., 1993.

She78

A. H. Sherman. NSPIV: a Fortran subroutine for sparse Gaussian elimination with partial pivoting. ACM Trans. Math. Softw., 4(4):391-398, December 1978.

She96

J. R. Shewchuk. Robust adaptive floating-point geometric predicates. In Proc. 12th ACM Computational Geometry, pages 141-150, 1996.

SK83

D. Sankoff and J. Kruskal. Time Warps, String Edits, and Macromolecules: the theory and practice of sequence comparison. Addison-Wesley, Reading MA, 1983.

SK86

T. Saaty and P. Kainen. The Four-Color Problem. Dover, New York, 1986.

SK93

R. Skeel and J. Keiper. Elementary Numerical computing with Mathematica. McGraw-Hill, New York, 1993.

Ski88

S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775-784, 1988.

Ski90

S. Skiena. Implementing Discrete Mathematics. Addison-Wesley, Redwood City, CA, 1990.

Sla61

P. Slater. Inconsistencies in a schedule of paired comparisons. Biometrika, 48:303-312, 1961.

SM73

L. Stockmeyer and A. Meyer. Word problems requiring exponential time. In Proc. Fifth ACM Symp. Theory of Computing, pages 1-9, 1973.

Smi91

D. M. Smith. A Fortran package for floating-point multiple-precision arithmetic. ACM Trans. Math. Softw., 17(2):273-283, June 1991.

Sou96

E. Southern. DNA chips: analysing sequence by hybridization to oligonucleotides on a large scale. Trends in Genetics, 12:110-115, 1996.

SPP76

A. Schönhage, M. Paterson, and N. Pippenger. Finding the median. J. Computer and System Sciences, 13:184-199, 1976.

SR83

K. Supowit and E. Reingold. The complexity of drawing trees nicely. Acta Informatica, 18:377-392, 1983.

SR95

R. Sharda and G. Rampal. Algebraic modeling languages on PCs. OR/MS Today, 22-3:58-63, 1995.

SS71

A. Schönhage and V. Strassen. Schnele multiplikation grosser zahlen. Computing, 7:281-292, 1971.

SS90

J. T. Schwartz and M. Sharir. Algorithmic motion planning. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 391-430. MIT Press, 1990.

SSS74

I. Sutherland, R. Sproull, and R. Shumacker. A characterization of ten hidden surface algorithms. ACM Computing Surveys, 6:1-55, 1974.

ST85

D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM, 32:652-686, 1985.

Sta90

J. Stasko. Tango: A framework and system for algorithm animation. Computer, 23:27-39, 1990.

Sta95

W. Stallings. Protect your Privacy: a guide for PGP Users. Prentice Hall PTR, Englewood Cliffs NJ, 1995.

Ste94

G. A. Stephen. String Searching Algorithms. Lecture-Notes-Series-on-Computing. World-Scientific-Publishing, October 1994.

Sto88

J. Storer. Data compression: methods and theory. Computer Science Press, Rockville MD, 1988.

Str69

V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14:354-356, 1969.

SV87

J. Stasko and J. Vitter. Pairing heaps: Experiments and analysis. Communications of the ACM, 30(3):234-249, 1987.

SV88

B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput., 17(6):1253-1262, December 1988.

SW86

D. Stanton and D. White. Constructive Combinatorics. Springer-Verlag, New York, 1986.

SW94

M. Stoer and F. Wagner. A simple min cut algorithm. In European Symp. Algorithms (ESA), volume 855, pages 141-147. Springer Verlag Lecture Notes in Computer Science, 1994.

SW95

J. Salowe and D. Warme. Thirty-five-point rectilinear Steiner minimal trees in a day. Networks: An International Journal, 25, 1995.

SWM95

J. Shallit, H. Williams, and F. Moraine. Discovery of a lost factoring machine. The Mathematical Intelligencer, 17-3:41-47, Summer 1995.

Tar95

G. Tarry. Le problème de labyrinthes. Nouvelles Ann. de Math., 14:187, 1895.

Tar72

R. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Computing, 1:146-160, 1972.

Tar75

R. Tarjan. Efficiency of a good by not linear set union algorithm. J. ACM, 22:215-225, 1975.

Tar79

R. Tarjan. A class of algorithms which require non-linear time to maintain disjoint sets. J. Computer and System Sciences, 18:110-127, 1979.

Tar83

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

Tho68

K. Thompson. Regular expression search algorithm. Communications of the ACM, 11:419-422, 1968.

Tho96

Mikkel Thorup. On RAM priority queues. In Proc. Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 59-67, 1996.

Tin90

G. Tinhofer. Generating graphs uniformly at random. Computing, 7:235-255, 1990.

Tro62

H. F. Trotter. Perm (algorithm 115). Comm. ACM, 5:434-435, 1962.

Tur88

J. Turner. Almost all k-colorable graphs are easy to color. J. Algorithms, 9:63-82, 1988.

TW88

R. Tarjan and C. Van Wyk. An O algorithm for triangulating a simple polygon. SIAM J. Computing, 17:143-178, 1988.

Ukk92

E. Ukkonen. Constructing suffix trees on-line in linear time. In Intern. Federation of Information Processing (IFIP '92), pages 484-492, 1992.

Vai88

P. Vaidya. Geometry helps in matching. In Proc. 20th ACM Symp. Theory of Computing, pages 422-425, 1988.

Val79

L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979.

Var91

I. Vardi. Computational Recreations in Mathematica. Addison-Wesley, Redwood City CA, 1991.

Vau80

J. Vaucher. Pretty printing of trees. Software Practice and Experience, 10:553-561, 1980.

vEBKZ77

P. van Emde Boas, R. Kaas, and E. Zulstra. Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99-127, 1977.

Veg90

G. Vegter. The visibility diagram: a data structure for visibility problems and motion planning. In Proc. second Scand. Workshop on Algorithm Theory (SWAT), volume 447, pages 97-110. Springer Verlag Lecture Notes in Computer Science, 1990.

Vit89

J. S. Vitter. Dynamic Huffman coding. ACM Trans. Math. Softw., 15(2):158-167, June 1989.

Viz64

V. G. Vizing. On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz, 3:23-30, 1964.

vL90a

J. van Leeuwen. Graph algorithms. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 525-631. MIT Press, 1990.

vL90b

J. van Leeuwen, editor. Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A. MIT Press, 1990.

vN63

J. von Neumann. Various techniques used in connection with random digits. In A. H. Traub, editor, John von Neumann, Collected Works, volume 5. Macmillan, 1963.

Vos92

S. Voss. Steiner's problem in graphs: heuristic methods. Discrete Applied Mathematics, 40, 1992.

War62

S. Warshall. A theorem on boolean matrices. J. ACM, 9:11-12, 1962.

Wat95

M. Waterman. Introduction to Computational Biology. Chapman Hall, London, 1995.

WBCS77

J. Weglarz, J. Blazewicz, W. Cellary, and R. Slowinski. An automatic revised simplex method for constrained resource network scheduling. ACM Trans. Math. Softw., 3(3):295-300, September 1977.

Wei73

P. Weiner. Linear pattern-matching algorithms. In Proc. 14th IEEE Symp. on Switching and Automata Theory, pages 1-11, 1973.

Wei92

M. Weiss. Data Structures and Algorithm Analysis. Benjamin/Cummings, Redwood City, CA, 1992.

Wel84

T. Welch. A technique for high-performance data compression. IEEE Computer, 17-6:8-19, 1984.

Wes83

D. H. West. Approximate solution of the quadratic assignment problem. ACM Trans. Math. Softw., 9(4):461-466, December 1983.

WF74

R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. ACM, 21:168-173, 1974.

Whi32

H. Whitney. Congruent graphs and the connectivity of graphs. American J. Mathematics, 54:150-168, 1932.

Wig83

A. Wigerson. Improving the performance guarantee for approximate graph coloring. J. ACM, 30:729-735, 1983.

Wil64

J. W. J. Williams. Algorithm 232 (heapsort). Communications of the ACM, 7:347-348, 1964.

Wil84

H. Wilf. Backtrack: An O(1) expected time algorithm for graph coloring. Info. Proc. Letters, 18:119-121, 1984.

Wil85

D. E. Willard. New data structures for orthogonal range queries. SIAM J. Computing, 14:232-253, 1985.

Wil89

H. Wilf. Combinatorial Algorithms: an update. SIAM, Philadelphia PA, 1989.

Win68

S. Winograd. A new algorithm for inner product. IEEE Trans. Computers, C-17:693-694, 1968.

Win80

S. Winograd. Arithmetic Complexity of Computations. SIAM, Philadelphia, 1980.

WM92a

S. Wu and U. Manber. Agrep - a fast approximate pattern-matching tool. In Usenix Winter 1992 Technical Conference, pages 153-162, 1992.

WM92b

S. Wu and U. Manber. Fast text searching allowing errors. Comm. ACM, 35:83-91, 1992.

Wol79

T. Wolfe. The Right Stuff. Bantam Books, Toronto, 1979.

Woo93

D. Wood. Data Structures, Algorithms, and Performance. Addison-Wesley, Reading MA, 1993.

WS79

C. Wetherell and A. Shannon. Tidy drawing of trees. IEEE Trans. Software Engineering, 5:514-520, 1979.

WW95

F. Wagner and A. Wolff. Map labeling heuristics: provably good and practically useful. In Proc. 11th ACM Symp. Computational Geometry, pages 109-118, 1995.

Yao81

A. C. Yao. A lower bound to finding convex hulls. J. ACM, 28:780-787, 1981.

Yao90

F. Yao. Computational geometry. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, pages 343-389. MIT Press, 1990.

YS96

F. Younas and S. Skiena. Randomized algorithms for identifying minimal lottery ticket sets. Journal of Undergraduate Research, 2-2:88-97, 1996.

YY76

A. Yao and F. Yao. The complexity of searching in an ordered random table. In Proc. 17th IEEE Symp. Foundations of Computer Science, pages 173-177, 1976.

ZL78

J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans. Information Theory, IT-23:337-343, 1978.