- Title
- Incremental network design with minimum spanning trees
- Creator
- Engel, Konrad; Kalinowski, Thomas; Savelsbergh, Martin W. P.
- Relation
- Funding BodyARCGrant NumberLP140101000 http://purl.org/au-research/grants/arc/LP140101000
- Relation
- Journal of Graph Algorithms and Applications Vol. 21, Issue 4, p. 417-432
- Publisher Link
- http://dx.doi.org/10.7155/jgaa.00423
- Publisher
- Brown University. Department of Computer Science
- Resource Type
- journal article
- Date
- 2017
- Description
- 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∖E0 minimizing [formula could not be replicated] where w(Xt) is the weight of a minimum spanning tree Xt for the subgraph (V,E0∪{e′1,…,e′t}) and T=|E∖E0|. We prove that this problem can be solved by a greedy algorithm.
- Subject
- network design; algorithm; math
- Identifier
- http://hdl.handle.net/1959.13/1353141
- Identifier
- uon:31033
- Identifier
- ISSN:1526-1719
- Rights
- © 2015. Originally published in Journal of Graph Algoithms and Applications.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1867
- Visitors: 2183
- Downloads: 370
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 469 KB | Adobe Acrobat PDF | View Details Download |