You are here
Computing a diameterconstrained minimum spanning tree
 Date Issued:
 2001
 Abstract/Description:
 University of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4 <= k <= (n  2), except when all edgeweights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a datastructure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space.
Title:  Computing a diameterconstrained minimum spanning tree. 
0 views
0 downloads 

Name(s): 
Abdalla, Ayman Mahmoud, Author Deo, Narsingh, Committee Chair Engineering and Computer Science, Degree Grantor 

Type of Resource:  text  
Date Issued:  2001  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  University of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4 <= k <= (n  2), except when all edgeweights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a datastructure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space.  
Identifier:  CFR0002215 (IID), ucf:52914 (fedora)  
Note(s): 
20010501 Ph.D. Electrical Engineering and Computer Science Doctorate This record was generated from author submitted information. Electronically reproduced by the University of Central Florida from a book held in the John C. Hitt Library at the University of Central Florida, Orlando. 

Subject(s): 
Algorithms Dissertations Academic  Engineering Engineering  Dissertations Academic Graph theory Trees (Graph theory) 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFR0002215  
Restrictions on Access:  public  
Host Institution:  UCF 