講演抄録/キーワード |
講演名 |
2012-12-10 10:55
次数制約付き点連結度ネットワーク設計問題に対する反復丸め近似アルゴリズム ○福永拓郎(京大) COMP2012-45 |
抄録 |
(和) |
本論文では,辺コストを持つグラフと次数の上限$b(\cdot)$が与えられたときに,指定された連結度要求を満たし,かつ各点$v$の次数が高々$b(v)$であるような最小コスト部分グラフを求める問題について議論する.本論文ではこの問題に対して反復丸め法に基づく近似アルゴリズムを与える.グラフが無向グラフであり,連結度要求が要素連結度に関するもので最大値$k$である場合,
提案アルゴリズムは近似比$O(k)$の辺コストを持ち点$v$の次数が$O(k) \cdot b(v)$以下であるような解を計算する. また,辺コストが与えられずに連結度要求と次数制約を満たす部分グラフを見つける問題についても議論し,同様のケースでは点$v$の次数が$6 b(v)+O(k^2)$以下であるような部分グラフをアルゴリズムが計算することを示す.これらのアルゴリズムは要素連結度要求の代わりに点連結度要求を持つ問題に対しても拡張することが可能である. |
(英) |
We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds $b(\cdot)$.
We present an iterative rounding algorithm for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value $k$, our algorithm computes a solution that is an $O(k)$-approximation for the edge cost in which the degree of each node $v$ is at most $O(k) \cdot b(v)$. We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node $v$ is at most $6 b(v)+O(k^2)$. These algorithms can be extended to other well-studied undirected node-connectivity requirements such as uniform, subset and rooted connectivity. |
キーワード |
(和) |
線形計画法 / 次数制約 / 点連結度 / ネットワーク設計問題 / 反復丸め法 / / / |
(英) |
degree bound / iterative rounding / linear programming / network design / node-connectivity / / / |
文献情報 |
信学技報, vol. 112, no. 340, COMP2012-45, pp. 15-22, 2012年12月. |
資料番号 |
COMP2012-45 |
発行日 |
2012-12-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-45 |