2010年11月
Network design with weighted degree constraints
Discrete Optimization
- ,
- 巻
- 7
- 号
- 4
- 開始ページ
- 246
- 終了ページ
- 255
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.disopt.2010.05.004
In an undirected graph G=(V,E) with a weight function w:E×V→Q+, the weighted degree dw(v
E) of a vertex v is defined as ∑w(e,v) |e∈Eincident tov. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on iterative rounding, which has been successfully applied to the degree-bounded network design problem. A problem of minimizing the maximum weighted degree of vertices is also discussed. © 2010 Elsevier B.V. All rights reserved.
E) of a vertex v is defined as ∑w(e,v) |e∈Eincident tov. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on iterative rounding, which has been successfully applied to the degree-bounded network design problem. A problem of minimizing the maximum weighted degree of vertices is also discussed. © 2010 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.disopt.2010.05.004
- ISSN : 1572-5286
- CiNii Articles ID : 120002511312
- SCOPUS ID : 77955517687