Edge-disjoint Undirected Spanning Trees on the Wrapped Butterfly Networks

Abstract

The problem of finding the maximum number of edgedisjoint spanning trees arises from the need for developing efficient collective communication algorithms in distributed memory parallel computers. In this paper, we propose a formula for obtaining the maximum number of edge-disjoint undirected spanning trees on the wrapped butterfly network. The result can be applied to design efficient multicast routing algorithms in wormhole-routed parallel systems.