The Algorithm Design Manual Second Edition

dations of Computer Science (FOCS), pages 549–554, 1989.

[JAMS91]

D. Johnson, C. Aragon, C. McGeoch, and D. Schevon. Optimization by

simulated annealing: an experimental evaluation; part II, graph coloring

and number partitioning. In Operations Research, volume 39, pages 378–

406, 1991.

[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, En-

glewood Cliffs NJ, 1988.

[JLR00]

S. Janson, T. Luczak, and A. Rucinski. Random Graphs. Wiley, 2000.

[JM93]

D. Johnson and C. McGeoch, editors. Network Flows and Matching: First

DIMACS Implementation Challenge, volume 12. American Mathematics So-

ciety, Providence RI, 1993.

[JM03]

M. J¨

unger and P. Mutzel. Graph Drawing Software. Springer-Verlag, 2003.

[Joh63]

S. M. Johnson. Generation of permutations by adjacent transpositions.

Math. Computation, 17:282–285, 1963.

[HUW02]

E. Haunschmid, C. Ueberhuber, and P. Wurzinger. Cache oblivious high

performance algorithms for matrix multiplication. Tech. Report AURORA

TR2002-08, Vienna University of Technology, 2002.

---

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

687

[Joh74]

D. Johnson. Approximation algorithms for combinatorial problems. J. Com-

puter 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, vol-

ume A, pages 67–162. MIT Press, 1990.

[Jon86]

D. W. Jones. An empirical comparison of priority-queue and event-set im-

plementations. Communications of the ACM, 29:300–311, 1986.

[Jos99]

N. Josuttis. The C++ Standard Library: A tutorial and reference. Addison-

Wesley, 1999.

[JR93]

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM J.

Computing, 22:1117–1141, 1993.

[JS01]

A. Jagota and L. Sanchis. Adaptive, restart, randomized greedy heuristics

for maximum clique. J. Heuristics, 7:1381–1231, 2001.

[JSV01]

M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation

algorithm for the permanent of a matrix with non-negative entries. In Proc.

33rd ACM Symp. Theory of Computing, pages 712–721, 2001.

[JT96]

D. Johnson and M. Trick. Cliques, Coloring, and Satisfiability: Second DI-

MACS Implementation Challenge, volume 26. AMS, Providence RI, 1996.

[KA03]

P. Ko and S. Aluru. Space-efficient linear time construction of suffix arrays,.

In Proc. 14th Symp. on Combinatorial Pattern Matching (CPM), pages 200–

210. Springer-Verlag LNCS, 2003.

[Kah67]

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

York, 1967.

[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.

[Kar96]

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.

[Kar00]

D. Karger. Minimum cuts in near-linear time. J. ACM, 47:46–76, 200.

[Kei00]

M. Keil. Polygon decomposition. In J.R. Sack and J. Urrutia, editors, Hand-