| No | 172963 |
|---|---|
| 標題（和） | 目標枝連結度3の最大被覆供給点配置問題 |
| 標題（英） | Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three |
| 研究会名（和） | 回路とシステム, 信号処理, 通信方式 |
| 研究会名（英） | Circuits and Systems, Signal Processing, Communication Systems |
| 開催年月日 | 2006-03-06 |
| 終了年月日 | 2006-03-07 |
| 会議種別コード | 5 |
| 共催団体名（和） | |
| 資料番号 | CAS2005-122, SIP2005-168, CS2005-115 |
| 抄録（和） | 与えられたグラフ$G=(V,E)$に対し，ある節点集合$S\\subseteq V$と節点$v\\in V$との間の枝連結度がある与えられた整数$k$以上のとき，$S$は$v$を被覆するとよぶ．また，$S$が含む節点のことを供給点とよぶ．本研究では，供給点配置問題を変形した問題である最大被覆供給点配置問題について扱う．本問題は，被覆される節点の重みの和が最大となるような，与えられた整数$p$個以下の供給点からなる節点集合$S$を見つける問題である．本研究では，節点の重みと枝容量を持った無向グラフ$G$に対し，$k=3$の場合における多項式時間アルゴリズムを示す． |
| 抄録（英） | Given a graph $G=(V,E)$, a set of vertices $S\\subseteq V$ covers a vertex $v\\in V$ if the edge-connectivity between $S$ and $v$ is at least a given number $k$. Vertices in $S$ are called sources. The maximum-cover source-location problem, which is a variation of the source location problem, is to find a source set $S$ with a given size at most $p$, maximizing the sum of the weight of vertices covered by $S$. In this paper, we show a polynomial-time algorithm for this problem in the case of $k=3$ when a vertex-weighted and edge-capacitated undirected graph is input. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.105, No.634,636,638 |
| ページ開始 | 25 |
| ページ終了 | 29 |
| キーワード（和） | 供給点配置問題,$k$-枝連結成分,枝連結度,動的計画法 |
| キーワード（英） | Source location problem,$k$-Edge-connected component,Edge-connectivity,Dynamic programming |
| 本文の言語 | ENG |
| 著者（和） | 杉原堅也 |
| 著者（ヨミ） | スギハラ ケンヤ |
| 著者（英） | Kenya Sugihara |
| 所属機関（和） | 京都大学 |
| 所属機関（英） | Kyoto University |
| 著者（和） | 伊藤大雄 |
| 著者（ヨミ） | イトウ ヒロオ |
| 著者（英） | Hiro Ito |
| 所属機関（和） | 京都大学 |
| 所属機関（英） | Kyoto University |