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

Connamacher, Harold S.
Proskurowski, Andrzej

Abstract

We investigate multi-source 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

Keywords

spanning tree
tree

Notes

Related Papers

Bibtex

 @unpublished {connamacher_span00,
   author = {Harold S. Connamacher and Andrzej Proskurowski},
    title = {The complexity of minimizing certain cost metrics for k-source spanning trees},
  note    = {To appear in Discrete Applied Mathematics}
}
Back to Intro By Author By Importance By Keyword By Title By Reference