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. In contrast, there exists 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. This chapter focuses on the approximation algorithms for constructing efficient communication spanning trees.