Erratum to : Incremental algorithms for the maximum internal spanning tree problem

Abstract

In the original paper [1], there are two errors on page 5.

The rules in the algorithm are not sufficient since we omitted one rule during publication. The following rule should be added to the paper.

Rule 3: If P1 = (u, v) and P2 = (x, y) are two maximal leaf-paths both with two vertices in T, where u and x are leaves in T and (v, y) ∈ E(G), we remove (y′, y) and then add (v, y) to T where y′ is the non-leaf neighbor of y in T.

The expression of Algorithm 2 is not accurate. It should be modified as follows.

Line 3: Exhaustively apply Rules 1–3, and for i ∈ {2, 3} only apply Rule i when none of Rules j where 1 ⩽ j < i is applicable.

Line 8: Determine the longest path P among all paths whose endpoints have nonempty neighbors in T \ V(T′).