Survivable Networks – Algorithms for Diverse Routing ERRATA
1. Step 3 of
Algorithm 3.2a has an error; after correction, it should read as: Find the first intermediate vertex from the destination vertex whose degree is greater than 2 (vertex F in Figure 3.16b). Replace the external
edges by arcs incident on this vertex (see Figure 3.16c).
2. Because greater than
3 has been corrected to greater than 2 in Step 3 of Algorithm 3.2a, Figure 3.18 in the monograph should be redrawn with vertex E split into two as
follows:
3. In Section 3.4.5, (Vertex-Splitting Method 2) should be replaced with (Vertex-Splitting Method 1).
Note: Algorithm 3.2a uses a completely different vertex-splitting trick from the standard vertex-splitting trick employed in Algorithm 3.2b. It was invented by the author as a direct extension of the edge-disjoint path algorithm (Algorithm 3.1) to a vertex-disjoint path algorithm.
Print 