# 重み付き次数制約を持つネットワーク設計問題 Network Design with Weighted Degree

## Abstract

In an undirected graph G=(V,E) with a weight function w:E×V→Q_+, the weighted degree d_w(v;E) of a vertex v∈V is defined as Σ{w(e,v)|e∈E incident with v}. In this paper, we consider a network design problem with the upper-bound on weighted degree of each vertex. Inputs of the problem are an undirected graph G=(V,E) with E=E_1∪^^・E_2∪^^・E_3, weights w_1:E_1×V→Q_+,μ:E_2→Q_+ and ν:E_3→Q_+, an edge-cost c:E→Q, and a degree-bound b:V→Q_+. A solution consists of a spanning tree T⊆E and weights w_i:T_i×V→Q_+ for i∈{2,3}, where T_i stands for T∩E_i. It is defined to be feasible if it satisfies w_2(e,u)+w_2(e,v)=μ(e) for e=uv∈T_2, {w_3(e,u),w_3(e, v)}={0,ν(e)} for e=uv∈T_3, and d_<w1>(v:T_1)+d_<w2>(v;T_2)+d_<w3>(v;T_3)≤b(v) for each v∈V. The goal of this problem is to find a feasible solution that minimizes its cost Σ_<e∈T>c(e). Relaxing the constraints on weighted degree, we propose bi-criteria approximation algorithms based on the iterative rounding. We also consider another problem that asks to minimize the maximum weighted degree of vertices.

## Journal

• IPSJ SIG Notes

IPSJ SIG Notes 118, 41-48, 2008-05-20

Information Processing Society of Japan (IPSJ)

## Codes

• NII Article ID (NAID)
110006793663
• NII NACSIS-CAT ID (NCID)
AN1009593X
• Text Lang
ENG
• Article Type
ART
• ISSN
09196072
• NDL Article ID
9525256
• NDL Call No.
Z14-1121
• Data Source
CJP  NDL  NII-ELS

Page Top