×

Spanning trees and optimization problems. (English) Zbl 1072.90047

Discrete Mathematics and its Applications. Boca Raton, FL: Chapman and Hall/CRC (ISBN 1-58488-436-3/hbk; 978-0-203-49728-9/ebook). xv, 184 p. (2004).
This monograph is devoted to spanning tree problems. After a chapter on counting spanning trees, the authors review classical spanning tree and shortest path algorithms. The following chapters – which form the main part of this monograph – deal with NP-hard problems in connection with spanning trees, such as minimum routing cost spanning trees, optimal communication spanning trees and balancing the tree costs. Special emphasis is laid on good approximation algorithms for these problems. Rather short sections on Steiner minimal trees, the diameter of trees and maximum leaf spanning trees conclude this book. At the end of every chapter the reader finds up-to-date bibliographic notes and suggestions for further reading as well as some exercises – altogether a useful text on optimization problems in connection with trees.

MSC:

90C35 Programming involving graphs or networks
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C27 Combinatorial optimization
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI