お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2006-05-24 10:40
Minimum Augmentation of Edge-Connectivity with Monotone Requirements in Undirected Graphs
Toshimasa IshiiOtaru Univ. of Commerce
抄録 (和) $V$を有限集合とする.$X' \subseteq X \subseteq V$であるどの集合$X, X'$についても,$r(X')\geq r(X)$が成立するとき,集合関数$r: 2^V \rightarrow Z^+$は単調であるという (但し,$Z^+$は非負整数集合を表わす).無向グラフ$G=(V,E)$と単調関数$r: 2^V \rightarrow Z^+$が与えられたとき, 最小本数の辺を加えることで,$G$を,$\{\emptyset,V\}$を除く全ての集合$X$について$d_{G'}(X)\geq r(X)$を満たすグラフ$G'$に増大させる問題を考える.ここで,$d_G(X)$は,$G$において$X$と$V-X$を結ぶ辺の数を表わす.この問題は,辺連結度増大問題や領域辺連結度増大問題を含む.領域辺連結度増大問題は一般にNP困難であると知られている問題である.本研究では,$r(X)>0$なら必ず$r(X)\geq 2$を満たすという仮定の下で,この問題が $O(n^4(m+n\log{n}))$時間で解けることを示す.ここで,$n=|V|$,$m=|\{\{u,v\}\mid (u,v)\in E\}|$である. 
(英) For a finite ground set $V$, we call a set-function $r: 2^V \rightarrow Z^+$ monotone, if $r(X')\geq r(X)$ holds for each $ X' \subseteq X \subseteq V$, where $Z^+$ is the set of nonnegative integers. Given an undirected multigraph $G=(V,E)$ and a monotone requirement function $r: 2^V \rightarrow Z^+$, we consider the problem of augmenting $G$ by a smallest number of new edges so that the resulting graph $G'$ satisfies $d_{G'}(X)\geq r(X)$ for each $\emptyset \neq X \subset V$, where $d_G(X)$ denotes the degree of a vertex set $X$ in $G$. This problem includes the edge-connectivity augmentation problem, and the node-to-area edge-connectivity augmentation problem which is known to be NP-hard.
In this paper, we show that the problem can be solved in $O(n^4(m+n\log{n}))$ time under the assumption that each $\emptyset \neq X \subset V$ satisfies $r(X)\geq 2$ whenever $r(X)>0$, where $n=|V|$ and $m=|\{\{u,v\}\mid (u,v)\in E\}|$.
キーワード (和) 無向グラフ / 辺連結度 / 連結度増大問題 / 単調関数 / / / /  
(英) undirected graph / edge-connectivity / connevtivity augmentation problem / monotone function / / / /  
文献情報 信学技報, vol. 106, no. 63, COMP2006-10, pp. 1-8, 2006年5月.
資料番号 COMP2006-10 
発行日 2006-05-17 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
PDFダウンロード

研究会情報
研究会 COMP  
開催期間 2006-05-24 - 2006-05-24 
開催地(和) 九州工業大学 
開催地(英) Kyushu Institute of Technology 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2006-05-COMP 
本文の言語 英語 
タイトル(和)  
サブタイトル(和)  
タイトル(英) Minimum Augmentation of Edge-Connectivity with Monotone Requirements in Undirected Graphs 
サブタイトル(英)  
キーワード(1)(和/英) 無向グラフ / undirected graph  
キーワード(2)(和/英) 辺連結度 / edge-connectivity  
キーワード(3)(和/英) 連結度増大問題 / connevtivity augmentation problem  
キーワード(4)(和/英) 単調関数 / monotone function  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 石井 利昌 / Toshimasa Ishii / イシイ トシマサ
第1著者 所属(和/英) 小樽商科大学 (略称: 小樽商科大)
Otaru University of Commerce (略称: Otaru Univ. of Commerce)
第2著者 氏名(和/英/ヨミ) / /
第2著者 所属(和/英) (略称: )
(略称: )
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2006-05-24 10:40:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2006-10 
巻番号(vol) IEICE-106 
号番号(no) no.63 
ページ範囲 pp.1-8 
ページ数 IEICE-8 
発行日 IEICE-COMP-2006-05-17 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会