Errata

Following is a list of corrections to the first printing of the book Algorithms on Trees and Graphs. The source code already incorporates these corrections.

Chapter 2. Algorithmic Techniques

Section 2.4, page 87:

(Submitted by Guangyi Wang on April 19, 2004.)

Replace

(and $A_1$ is transformed to $T_1$)
by
(and $A_1$ is transformed to $T_2$)

Chapter 4. Tree Isomorphism

Definition 4.1, page 152:

(Submitted by the author on November 19, 2004.)

Replace

$\mathit{first}[v]=\mathit{first}[w]$
by
$(\mathit{first}[v],\mathit{first}[w]) \in M$

and replace

$\mathit{next}[v]=\mathit{next}[w]$
by
$(\mathit{next}[v],\mathit{next}[w]) \in M$

Definition 4.4, page 157:

(Submitted by Michael Kanellos on November 19, 2004.)

Replace

$\mathit{parent}[v]=\mathit{parent}[w]$
by
$(\mathit{parent}[v],\mathit{parent}[w]) \in M$

Lemma 4.61, page 235:

(Submitted by Liliana Félix on December 27, 2005.)

Replace

The algorithm for bottom-up unordered subtree isomorphism
by
The algorithm for bottom-up unordered maximum common subtree isomorphism

Chapter 6. Clique, Independent Set, and Vertex Cover

Section 6.1, page 305:

(Submitted by Nils Kriege on December 20, 2010.)

Replace label v5 along the v3 v4 v5 v7 path in Fig. 6.3 by v6.

Section 6.2, pages 327 and 331:

(Submitted by the author on October 14, 2002.)

Replace

bool independent;
by
bool independent = false;

Section 6.3, page 337:

(Submitted by the author on October 6, 2003.)

Replace

if ( T.number_of_nodes() == 1 ) {
  C.insert(T.first_node() );
} else {
by either
if ( T.number_of_nodes() == 1 ) {
  // C.insert(T.first_node() );
} else {
or
if ( T.number_of_nodes() != 1 ) {

Section 6.3, page 339:

(Submitted by the author on October 6, 2003.)

Replace

if ( G.number_of_nodes() == 1 ) {
  C.insert(G.first_node() );
} else {
by either
if ( G.number_of_nodes() == 1 ) {
  // C.insert(G.first_node() );
} else {
or
if ( G.number_of_nodes() != 1 ) {

Chapter 7. Graph Isomorphism

Section 7.1.1, page 358:

(Submitted by Peter Billen on March 30, 2005.)

Replace

( A1(v,w) != nil && A2(M[v],M[w]) == nil && G1[A1(v,w)] != G2[A2(M[v],M[w])] )
by
( A1(v,w) != nil && A2(M[v],M[w]) != nil && G1[A1(v,w)] != G2[A2(M[v],M[w])] )

Section 7.3.1, page 369:

(Submitted by Andreas Möller on January 14, 2003.)

Replace

hold for all vertices $x \in V_1 \setminus V$ and $y \in V_2 \setminus W$.
by
hold for all vertices $x \in V_1$ and $y \in W$ with $(x,y) \in M$.