| Title: | FINDING SPANNING TREE MINIMIZING THE MAXIMUM EDGE LOAD |
| Author: | Raina, Siddharth K |
| Description: | A communication network is often modeled as a graph and various algorithms are used to optimize its certain characteristics, solution to which bears a spanning tree. With different aspects, there are different measurements of the goodness of a spanning tree. MRCT though minimizes the average communication cost between all pair of nodes there may be large differences in the load on different links in the tree. In this thesis, our primary goal is to present and compare different heuristics for finding a spanning tree T=(V,U) such that largest edge load of T is minimized among all possible tree. In this thesis, we propose four heuristics based on well known algorithms. We run these heuristics on graphs based on well known topologies such as Waxman and Power-law. On comparing we find that Bi-partite semi matching heuristic outperforms other heuristics considered and Max-leaf tree heuristic on an average fetches worst result. |
| Bookmark: |
http://rave.ohiolink.edu/etdc/view?acc_num=kent1163803012
http://hdl.handle.net/123456789/5576 |
| Date: | 2006 |
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||