Spanning Trees and Optimization Problems: 1st Edition (Hardback) book cover

Spanning Trees and Optimization Problems

1st Edition

By Bang Ye Wu, Kun-Mao Chao

Chapman and Hall/CRC

200 pages | 67 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781584884361
pub: 2004-01-27
SAVE ~$20.25
$135.00
$114.75
x


FREE Standard Shipping!

Description

The design of approximation algorithms for spanning tree problems has become an exciting and important area of theoretical computer science and also plays a significant role in emerging fields such as biological sequence alignments and evolutionary tree construction. While work in this field remains quite active, the time has come to collect under one cover spanning tree properties, classical results, and recent research developments.

Spanning Trees and Optimization Problems offers the first complete treatment of spanning tree algorithms, from their role in classical computer science to their most modern applications. The authors first explain the general properties of spanning trees, then focus on three main categories: minimum spanning trees, shortest-paths trees, and minimum routing cost spanning trees. Along with the theoretical descriptions of the methods, numerous examples and applications illustrate the concepts in practice. The final chapter explores several other interesting spanning trees, including maximum leaf spanning trees, minimum diameter spanning trees, Steiner trees, and evolutionary trees.

With logical organization, well chosen topics, and easy to understand pseudocode, the authors provide not only a full, rigorous treatment of theory and applications, but also an excellent handbook for spanning tree algorithms. This book will be a welcome addition to your reference shelf whether your interests lie in graph and approximation algorithms for theoretical work or you use graph techniques to solve practical problems

Reviews

"… will supplement nicely undergraduate courses in discrete mathematics and graph theory … Summing Up: … Recommended for upper-division undergraduates through faculty."

- CHOICE, November 2004, Vol. 42, No. 3

Table of Contents

SPANNING TREES

Counting Spanning Trees

MINIMUM SPANNING TREES

Introduction

Bor°uvka's Algorithm

Prim's Algorithm

Kruskal's Algorithm

Applications

Summary

Bibliographic Notes and Further Reading

Exercises

SHORTEST-PATHS TREES

Introduction

Dijkstra's Algorithm

The Bellman-Ford Algorithm

Applications

Summary

Bibliographic Notes and Further Reading

Exercises

MINIMUM ROUTING COST SPANNING TREES

Introduction

Approximating by a Shortest-Paths Tree

Approximating by a General Star

A Reduction to the Metric Case

A Polynomial Time Approximation Scheme

Applications

Summary

Bibliographic Notes and Further Reading

Exercises

OPTIMAL COMMUNICATION SPANNING TREES

Introduction

Product-Requirement

Sum-Requirement

Multiple Sources

Applications

Summary

Bibliographic Notes and Further Reading

Exercises

BALANCING THE TREE COSTS

Introduction

Light Approximate Shortest-Paths Trees

Light Approximate Routing Cost Spanning Trees

Applications

Summary

Bibliographic Notes and Further Reading

Exercises

STEINER TREES AND SOME OTHER PROBLEMS

Steiner Minimal Trees

Trees and Diameters

Maximum Leaf Spanning Trees

Some Other Problems

Bibliographic Notes and Further Reading

Exercises

REFERENCES

INDEX

About the Series

Discrete Mathematics and Its Applications

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM046000
COMPUTERS / Operating Systems / General
COM051300
COMPUTERS / Programming / Algorithms
MAT036000
MATHEMATICS / Combinatorics