ABSTRACT
A spanning tree for a graph G is a subgraph of G that is a tree and contains all the vertices of G. Besides numerous network design applications, spanning trees also play important roles in several newly established research areas, such as biological sequence alignments and evolutionary tree construction. On the other hand, there exist many spanning tree problems that have been proved to be NP-hard. Thus, designing approximation algorithms for those hard spanning-tree problems has become an exciting and important field in theoretical computer science. The current chapter focuses on the approximation algorithms for constructing efficient communication spanning trees.
