## Abstract

Edge-independent spanning trees (EISTs) have important applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution, thus their designs in several classes of networks have been widely investigated. The n-dimensional augmented cube (AQ_{n}) is an important variant of the n-dimensional hypercube. It is (2n−1)-regular, (2n−1)-connected (n≠3), vertex-symmetric and has diameter of ⌈n/2⌉. In this paper, by proposing an O(NlogN) algorithm that constructs 2n−1 EISTs in AQ_{n}, where N is the number of nodes in AQ_{n}, we solve the EISTs problem for this class of graphs. Since AQ_{n} is (2n−1)-regular, the result is optimal with respect to the number of EISTs constructed.

Original language | English |
---|---|

Pages (from-to) | 23-32 |

Number of pages | 10 |

Journal | Theoretical Computer Science |

Volume | 670 |

DOIs | |

Publication status | Published - 29 Mar 2017 |

Externally published | Yes |

## Keywords

- Algorithm
- Augmented cubes
- Edge independent spanning trees
- Fault-tolerance