Incremental Network Design with Minimum Spanning Trees

Konrad Engel; Thomas Kalinowski; Martin W P Savelsbergh

doi:10.7155/jgaa.00423

Incremental Network Design with Minimum Spanning Trees

Konrad Engel, Thomas Kalinowski, Martin W P Savelsbergh

School of Science & Technology

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

Abstract

Given an edge-weighted graph G = (V,E) and a set E₀⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ ₁ , … , e ′ _T ∈ E ∖ E ₀ minimizing ∑ ^T _{t = 1} w ( X _t ) where w(X_t) is the weight of a minimum spanning tree X_t for the subgraph (V,E₀∪ { e ′ ₁ , … , e ′ _T } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.

Original language	English
Pages (from-to)	417-432
Journal	Journal of Graph Algorithms and Applications
Volume	21
Issue number	4
DOIs	https://doi.org/10.7155/jgaa.00423
Publication status	Published - 28 Feb 2017

Access to Document

10.7155/jgaa.00423

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

Handle.net

Persistent link

Cite this

@article{fa7d8aac59224da3abd6039c548c4785,

title = "Incremental Network Design with Minimum Spanning Trees",

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.",

author = "Konrad Engel and Thomas Kalinowski and Savelsbergh, \{Martin W P\}",

year = "2017",

month = feb,

day = "28",

doi = "10.7155/jgaa.00423",

language = "English",

volume = "21",

pages = "417--432",

journal = "Journal of Graph Algorithms and Applications",

issn = "1526-1719",

publisher = "Brown University, Department of Computer Science",

number = "4",

}

TY - JOUR

T1 - Incremental Network Design with Minimum Spanning Trees

AU - Engel, Konrad

AU - Kalinowski, Thomas

AU - Savelsbergh, Martin W P

PY - 2017/2/28

Y1 - 2017/2/28

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85021667365

U2 - 10.7155/jgaa.00423

DO - 10.7155/jgaa.00423

M3 - Article

SN - 1526-1719

VL - 21

SP - 417

EP - 432

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 4

ER -

Incremental Network Design with Minimum Spanning Trees

Abstract

Access to Document

Handle.net

Fingerprint

Cite this