The Algorithm Design Manual Second Edition

tures, Sorting, Searching, and Graph Algorithms. Addison-Wesley, Reading

MA, third edition, 1998.

[Sei04]

R. Seidel. Convex hull computations. In J. Goodman and J. O’Rourke,

editors, Handbook of Discrete and Computational Geometry, pages 495–512.

CRC Press, 2004.

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

---

702

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

[SFG82]

M. Shore, L. Foulds, and P. Gibbons. An algorithm 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.

[SH99]

W. Shih and W. Hsu. A new planarity test. Theoretical Computer Science,

223(1–2):179–191, 1999.

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

[Sha04]

M. Sharir. Algorithmic motion planning. In J. Goodman and J. O’Rourke,

editors, Handbook of Discrete and Computational Geometry, pages 1037–

1064. CRC Press, 2004.

[She97]

J. R. Shewchuk. Robust adaptive floating-point geometric predicates. Disc.

Computational Geometry, 18:305–363, 1997.

[Sho05]

V. Shoup. A Computational Introduction to Number Theory and Algebra.

Cambridge University Press, 2005.

[Sip05]

M. Sipser. Introduction to the Theory of Computation. Course Technology,

second edition, 2005.

[SK86]

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

[SK99]

D. Sankoff and J. Kruskal. Time Warps, String Edits, and Macromolecules:

the theory and practice of sequence comparison. CSLI Publications, Stanford

University, 1999.

[SK00]

R. Skeel and J. Keiper. Elementary Numerical computing with Mathematica.

Stipes Pub Llc., 2000.

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

[Ski99]

S. Skiena. Who is interested in algorithms and why?: lessons from the stony

brook algorithms repository. ACM SIGACT News, pages 65–74, September

1999.

[SL07]

M. Singh and L. Lau. Approximating minimum bounded degree spanning

tree to within one of optimal. In Proc. 39th Symp. Theory Computing

(STOC), pages 661–670, 2007.

[SLL02]

J. Siek, L. Lee, and A. Lumsdaine. The Boost Graph Library: user guide

and reference manual. Addison Wesley, Boston, 2002.

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

metic. ACM Trans. Math. Softw., 17(2):273–283, June 1991.

[Sno04]

J. Snoeyink. Point location. In J. Goodman and J. O’Rourke, editors, Hand-

book of Discrete and Computational Geometry, pages 767–785. CRC Press,

2004.

---

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

703

[SR83]

K. Supowit and E. Reingold. The complexity of drawing trees nicely. Acta