ERRATA for MORET and SHAPIRO's text "ALGORITHMS FROM P TO NP, VOL. I"
---------------------------------------------------------------------

PREFACE:
page vi, line 11:  ", algorithms" should be removed

CHAPTER 1:
page 50, Even [1979] should be Even [1980]

CHAPTER 2:
page 63, 2nd paragraph (before 2.2): the ellipsis (...) should be followed
	by a comma
page 68, 5 lines from bottom: remove the last part of the first sentence
	", namely $Q_k(n) \cdot b^n$."
page 69, 3rd equation from the bottom (4th from the top): the term \beta_2 n
        should have a coefficient of 2, not the implied 1.
page 80, "first order linear differential..." should be "first-order linear
	differential..."

CHAPTER 3:
p. 146-147: 2^n should be 2^m (3 occurrences within the paragraph, plus an n
	that should be m))
p. 146, Strictly speaking, the amortized cost of insertion is constant,
        as can be shown by a suitable choice of potential function (number of
        T_k trees); in the example given, while the actual cost of each
        insertion is logarithmic, all of it can be charged to the deletemins;
        this amortized cost, however, is somewhat misleading---in the spirit
        of Exercise 3.21.
p. 157, bottom line: spacing between "the" and "representative" too large
p. 159, 2nd paragraph of proof, last line: "which" should be "that"
p. 159, 3rd paragraph of proof, 5th line: "that" should be "which"
p. 186, "Knuth [1973b]" should read "Knuth [1973]" (2 occurrences)
p. 187, "Knuth [1973a]" should read "Knuth [1973]" (1 occurrence)

CHAPTER 4:
Figure 4.11, p. 227: missing vertical bar through right endpoint of H segment
        move character G to the right as a consequence
p. 238, 2nd paragraph, 5th line: missing period at end of sentence
	("...linear time A..." should be "... linear time.  A...")
p. 252, Exercise 4.37: the hint is misleading; remove it.

CHAPTER 5:
p. 311, Figure 5.12: the second set should be labeled X-Y, not X (in both parts)
p. 324, 2nd paragraph of bibliography: replace the entire sentence beginning
	with "Some of the fast algorithms..." with the new sentence
	"Some of the fast algorithms for the problem can be found in
	Cheriton and Tarjan [1976], Fredman and Tarjan [1984], and
	Gabow et al. [1989]; the fastest is due to Gabow et al. [1986]:
	it runs in O(|E|log beta(|E|,|V|) time."
p. 324, last paragraph; reference to Fredman and Tarjan [1987] should really
	be to Fredman and Tarjan [1984] (reference entry is missing, see below)
p. 325, 2nd paragraph: reference to Korte and Lovasz should include all three
	papers, i.e., should be Korte and Lovasz [1981, 1984, 1986].
p. 325, last paragraph; add sentence
	"A solution to Exercise 5.24 appears in Edmonds and Karp [1972]."

CHAPTER 6:
p. 345, remove white space at top of page

CHAPTER 7:
p. 457, Figure 7.14, the S_k point is too high and the P_2 point too far
	to the right.
p. 462, 2nd paragraph, parenthetical remark: remove comma after "at least"
P. 463, equation in Section 7.3; the running sum is over n, not over i
p. 484, Exercise 7.8, part 3: should be "product of two nxn matrices",
	instead of "product of 2 nxn matrices"

CHAPTER 8:
p. 543, Exercise 8.5, first line: "Shell's methods" should read "Shell's method"
p. 549, last line: "For detail on..." should read "For details on..."

REFERENCES:
p. 550, AH&U's two references out of chronological order
p. 552, Edmonds [1963] out of chronological order
p. 553, Gabow et al. [1984]; change to [1989] and remove the FOCS citation,
	keeping only the JACM citation
p. 557, Lewis & Denenberg's title inverted
p. 558, remove Overmars and van Leeuwen [1981] (never used in the text)
p. 559, Sleator and Tarjan [1986]: "Self-Adjusting" should read "Self-adjusting"
p. 560, two of Tarjan's references switched out of chronological order

MISSING REFERENCES:
-- referenced as Ford and Fulkerson [1956] in 6.7
     Ford, L.R. Jr., and D.R. Fulkerson [1956],
     ``Maximal flow through a network,''
     Can. J. Math. 8, pp. 399--404.
-- referenced as Ford and Fulkerson [1962] in 1.9 and 6.7
     Ford, L.R. Jr., and D.R. Fulkerson [1962],
     Flows in Networks.
     Princeton U. Press, Princeton, NJ.
-- referenced as Fredman et al. [1986] in 3.5
     Fredman, M.L., R. Sedgewick, D.D. Sleator, and R.E. Tarjan [1986],
     ``The pairing heap: a new form of self-adjusting heap,''
     Algorithmica 1, pp. 111--129.
-- referenced as Fredman and Spencer [1987] in 3.5
     Fredman, M.L., and T.H. Spencer [1987],
     ``Refined complexity analysis for heap operations,''
     J. Comput. Syst. Sci. 35, pp. 269--284.
-- referenced as Fredman and Tarjan [1984] in 3.5 and (corrected) in 5.8
     Fredman, M.L., and R.E. Tarjan [1984],
     ``Fibonacci heaps and their use in improved network optimization algorithms,''
     Proc. 25th Ann. IEEE Symp. Foundations Comput. Sci. FOCS-84, pp. 338--346;
     in final form in J. ACM 34 (1987), pp. 596--615.
-- referenced as Jones [1989] in 3.5
     Jones, D.W. [1989],
     ``Concurrent operations on priority queues,''
     Commun. ACM 32, pp. 132--137.


UPDATING for MORET and SHAPIRO's text "ALGORITHMS FROM P TO NP, VOL. I"
-----------------------------------------------------------------------

CHAPTER 1:
Steiner trees: it has now been proved that the example given in Figure 1.16
is a worst-case example for spanning trees, thereby solving Exercise 1.13
exactly.  (The very complex proof is due to F.K. Hwang and D. Du,
Proc. Nat'l Academy of Sciences 87 (23), December 90; also in FOCS 90.)

CHAPTER 4:
Triangulation, and thus simplicity testing, can now be done in linear time,
although the algorithm is very complex (Chazelle, Princeton CS-TR-264-90,
also in FOCS 1990)

CHAPTER 5:
Fredman and Willard (FOCS 1990) have given a linear-time algorithm for MST;
their paper also gives an improved algorithm for the shortest path problem.

CHAPTER 6:
Alt et al. (Inf. Process. Lett. 37, 1991) have given a bipartite matching
algorithm that runs in O(|V|\sqrt{|E||V|/log|V|}) and thus outperforms
the O(|E|\sqrt{|V|}) algorithm on very dense graphs.