Spanning Trees and Optimization Problems

By Bang Ye Wu (吳邦一) and Kun-Mao Chao (趙坤茂)

Series: Discrete Mathematics and Its Applications Volume: 26
ISBN: 1584884363
Publication Date: 1/27/2004
Number of Pages: 200
Chapman & Hall / CRC

Errata:

P. 33 (line -5): i <- 0 ==> i <- 1
P. 34 (line 14): the BELLMAN-FORD ==> the BELLMAN-FORD algorithm
P. 45 (line 8): graph ==> tree?
(It's not necessary! "Graph" is also fine. Recall that the term "distance" means "the length of the shortest path.")
P. 50 (line 13): a same branch ==> the same branch
P. 55 (line 10): Lemma 4.2 ==> Corollary 4.2
P. 63 (line -4); P. 64 (line -8): T ==> T hat
P. 104 (line -3): 2 (r(T_u)+r(T_v)) ==> 2 (r(T_u)|T_v|+r(T_v)|T_u|)
P. 106 (line -3): <= ==> = (It's better to switch u and v in line -4.)
P. 107 (line -5): for any vertex u
(Here we root T at P. The "branch" means a component in the graph resulted by removing P.)
P. 125 (line -6): OCT problem ==> the OCT problem
P. 149 (line 7):
\textbf{for} each edge $e=(u,v)\in E(T_L)$ \textbf{do} ==>
\textbf{for} each edge $e=(u,v)\in E(T_L)$  in a depth-first-search order of $T_L$ \textbf{do} \\
(We thank Pallavi Jayawant and Duane Pelz for pointing out this error. Should the edges be processed in an arbitrary order, the output might not be a connected graph.)
P. 150 (line 2): w(tsp(G_L))==> \bar{w}(tsp(G_L))
P. 150 (lines 2 & 5): w(T_L) ==> \bar{w}(T_L) (two places)
P. 151 (line 10): w(mst(G_L)) ==> \bar{w}(mst(G_L))
P. 152 (line -9): 12 --> 11; Some sentences need to be fixed accordingly.
P. 153 (line -1): w(mst(G_L)) ==> \bar{w}(mst(G_L))
P. 154 (lines 2 & 3): w(mst(G_L)) ==> \bar{w}(mst(G_L)) (two places)
P. 157 (lines 1 & 2):
As a result, $d_T(v_3,v_2)=d_T(v_1,v_2)$ and $SP_T(v_3,v_2)$ is also a diameter.

==>

If $u_1=u_2$, then $d_T(v_3,v_1)=d_T(v_1,v_2)$ and $SP_T(v_3,v_1)$ is also a diameter. Otherwise, $d_T(v_3,v_2)=d_T(v_1,v_2)$ and $SP_T(v_3,v_2)$ is also a diameter.

P. 158 (Figure 7.6 (a)): Remove the branches under vertex v_2
P. 159 (line 5): a MDST ==> an MDST
P. 179 (Ref. 74, line 2): inlinear ==> in linear