The efficient construction of edge-independent spanning trees (EISTs) is interesting in itself, but also has important applications in network communications, for example, protocol design, secure communication, and fault-tolerant communication.

Although problematic for arbitrary graphs, efficient EIST construction has been shown to be possible for various specific kinds of graphs. This paper presents an O(N log N) algorithm to construct EISTs for augmented cubes.

The paper is remarkably readable given the technical nature of the subject area. Section 2 provides definitions and lemmas, usefully illustrated by clear and informative figures. This is followed in section 3 by a presentation of the algorithm with a proof of its correctness. The algorithm could be made more readable by including comments that refer to the relevant definitions. That said, useful diagrams and commentary provide clear explanations of the algorithm. The proof of correctness is broken down into several lemmas and theorems. Individual proofs could be made more readable if more white space were used in the layout.

Overall, this is a useful paper that is likely to be of interest to anyone concerned with communication networks.