The complexity of minimizing certain cost metrics for k-source spanning trees

We investigate multisource spanning tree problems where, given a graph with edge weights and a subset of the nodes defined as sources, the object is to find a spanning tree of the graph that minimizes some distance-related cost metric. This problem can be used to model multicasting in a network wher...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2003-09, Vol.131 (1), p.113-127
Main Authors: Connamacher, Harold S., Proskurowski, Andrzej
Format: Article
Language:English
Subjects:
Calculus of variations and optimal control
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematical analysis
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate multisource spanning tree problems where, given a graph with edge weights and a subset of the nodes defined as sources, the object is to find a spanning tree of the graph that minimizes some distance-related cost metric. This problem can be used to model multicasting in a network where messages are sent from a fixed collection of senders and communication takes place along the edges of a single spanning tree. For a limited set of possible cost metrics of such a spanning tree, we either prove the problem is NP-hard or we demonstrate the existence of an efficient algorithm to find an optimal tree.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(02)00420-1