Incremental Network Design with Minimum Spanning Trees

Title
Incremental Network Design with Minimum Spanning Trees
Publication Date
2017-02
Author(s)
Engel, Konrad
Kalinowski, Thomas
( author )
OrcID: https://orcid.org/0000-0002-8444-6848
Email: tkalinow@une.edu.au
UNE Id une-id:tkalinow
Savelsbergh, Martin W P
Type of document
Journal Article
Language
en
Entity Type
Publication
Publisher
Brown University, Department of Computer Science
Place of publication
United States of America
DOI
10.7155/jgaa.00423
UNE publication id
une:1959.11/26781
Abstract
Given an edge-weighted graph G = (V,E) and a set E0⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ 1 , … , e ′ T ∈ E ∖ E 0 minimizing ∑ T t = 1 w ( X t ) where w(Xt) is the weight of a minimum spanning tree Xt for the subgraph (V,E0∪ { e ′ 1 , … , e ′ T } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.
Link
link
Citation
Journal of Graph Algorithms and Applications, 21(4), p. 417-432
ISSN
1526-1719
Start page
417
End page
432

Files:

NameSizeformatDescriptionLink