Wednesday, April 8, 2009


This work provides an empirical study of existing and new algorithms for the degree-bounded minimum spanning tree problem with a focus on improving the result for average-latency within the constraint of tree compactness. We have presented a new algorithm for approximation of degree-bounded minimum spanning trees with and without hop (tree depth) constraints. Of the three algorithms tested, DBSPT-Circular-PO delivers the best result for the criteria of average-latency and maximum hop count while
forming compact B-ary trees on different network topologies.
Experimentally, DBSPT-Circular shows an improvement in average-latency between 1.0% and 8.2% for the networks tested (this includes all sizes tested).
DBSPT-Circular-PO performs the best in terms of the bicriteria problem (as described earlier)for the average-latency and average-depth.

No comments:

my traffic rate

Hire Me Direct