Engel, Konrad; Kalinowski, Thomas; Savelsbergh, Martin W P

Author(s)

Engel, Konrad

Kalinowski, Thomas

Savelsbergh, Martin W P

Publication Date

2017-02

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.

Citation

Journal of Graph Algorithms and Applications, 21(4), p. 417-432

ISSN

1526-1719

Link

https://hdl.handle.net/1959.11/26781

Publisher

Brown University, Department of Computer Science

Title

Incremental Network Design with Minimum Spanning Trees

Type of document

Journal Article

Entity Type

Publication

Author(s)	Engel, Konrad Kalinowski, Thomas Savelsbergh, Martin W P
Publication Date	2017-02
Abstract	Given an edge-weighted graph G = (V,E) and a set E<sub>0</sub>⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ <sub>1</sub> , … , e ′ <sub>T</sub> ∈ E ∖ E <sub>0 </sub> minimizing ∑ <sup>T</sup> <sub> t = 1</sub> w ( X <sub>t</sub> ) where w(X<sub>t</sub>) is the weight of a minimum spanning tree X<sub>t</sub> for the subgraph (V,E<sub>0</sub>∪ { e ′ <sub>1</sub> , … , e ′ <sub>T</sub> } ) and T=\|E∖ E 0 \|. We prove that this problem can be solved by a greedy algorithm.
Citation	Journal of Graph Algorithms and Applications, 21(4), p. 417-432
ISSN	1526-1719
Link	https://hdl.handle.net/1959.11/26781
Publisher	Brown University, Department of Computer Science
Title	Incremental Network Design with Minimum Spanning Trees
Type of document	Journal Article
Entity Type	Publication

Incremental Network Design with Minimum Spanning Trees

Files: