 |
| Home | Issues | About JGAA | Instructions for Authors |
|
DOI: 10.7155/jgaa.00423
Incremental Network Design with Minimum Spanning Trees
Vol. 21, no. 4, pp. 417-432, 2017. Regular paper.
Abstract Given an edge-weighted graph $G=(V,E)$ and a set $E_0\subset E$, the incremental network design
problem with minimum spanning trees asks for a sequence of edges $e'_1,\ldots,e'_T\in E\setminus
E_0$ minimizing $\sum_{t=1}^Tw(X_t)$ where $w(X_t)$ is the weight of a minimum spanning tree $X_t$
for the subgraph $(V,E_0\cup\{e'_1,\ldots,e'_t\})$ and $T=\lvert E\setminus E_0\rvert$. We prove
that this problem can be solved by a greedy algorithm.
|
Submitted: June 2016.
Reviewed: November 2016.
Revised: January 2017.
Accepted: January 2017.
Final: January 2017.
Published: February 2017.
Communicated by
Joseph S. B. Mitchell
|
Journal publisher
|
Journal network
|
Journal Supporters
|
