Downloads: 184

Files in This Item:
File Description SizeFormat 
j.disopt.2010.05.004.pdf197.25 kBAdobe PDFView/Open
Title: Network design with weighted degree constraints
Authors: Fukunaga, Takuro
Nagamochi, Hiroshi  kyouindb  KAKEN_id
Author's alias: 福永, 拓郎
Keywords: Connectivity
Degree constraint
Iterative rounding
Network design
Spanning tree
Issue Date: Nov-2010
Publisher: Elsevier B.V.
Journal title: Discrete Optimization
Volume: 7
Issue: 4
Start page: 246
End page: 255
Abstract: 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 ∈ E incident to v}. 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 the iterative round-ing, 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.
Rights: © 2010 Elsevier B.V.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/128835
DOI(Published Version): 10.1016/j.disopt.2010.05.004
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.