Algorithms for the optimum communication spanning tree problem

Prabha Sharma ()

Annals of Operations Research, 2006, vol. 143, issue 1, 203-209

Abstract: Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements r ij and a set of distances d ij for all pair of nodes (i,j), the cost of communication for a pair of nodes (i,j), with respect to a spanning tree T is defined as r ij times the length of the unique path in T, that connects nodes i and j. Total cost of communication for a spanning tree is the sum of costs for all pairs of nodes of G. The problem is to construct a spanning tree for which the total cost of communication is the smallest among all the spanning trees of G. The problem is known to be NP-hard. Hu (1974) solved two special cases of the problem in polynomial time. In this paper, using Hu’s result the first algorithm begins with a cut-tree by keeping all d ij equal to the smallest d ij . For arcs (i,j) which are part of this cut-tree the corresponding d ij value is increased to obtain a near optimal communication spanning tree in pseudo-polynomial time. In case the distances d ij satisfy a generalised triangle inequality the second algorithm in the paper constructs a near optimum tree in polynomial time by parametrising on the r ij . Copyright Springer Science + Business Media, Inc. 2006

Keywords: Cost of communication; Cut-tree; Star-tree; Adjacent spanning tree; Adjacent basic feasible solution (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-7382-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:143:y:2006:i:1:p:203-209:10.1007/s10479-006-7382-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-006-7382-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().