無向グラフにおける単調な要求関数を持つ辺連結度増大問題
スポンサーリンク
概要
- 論文の詳細を見る
Vを有限集合とする.X'⫅X⫅Vであるどの集合X,X'についても,r(X')≧r(X)が成立するとき,集合関数r:2^V→Z^+は単調であるという(但し,Z^+は非負整数集合を表わす).無向グラフG=(V,E)と単調関数r:2^V→Z^+が与えられたとき,最小本数の辺を加えることで,Gを,{∅,V}を除く全ての集合Xについてd_<G'>(X)≧r(X)を満たすグラフG'に増大させる問題を考える.ここで,d_G(X)は,GにおいてXとV-Xを結ぶ辺の数を表わす.この問題は,辺連結度増大問題や領域辺連結度増大問題を含む.領域辺連結度増大問題は一般にNP困難であると知られている問題である.本研究では,r(X)>0なら必ずr(X)≧2を満たすという仮定の下で,この問題がO(n^4(m+n logn))時間で解けることを示す.ここで,n=|V|, m=|{{u,v}|(u,v)⋳E}|である.
- 社団法人電子情報通信学会の論文
- 2006-05-17
著者
関連論文
- 点集合間の辺連結度を増大させる問題
- 平成20年秋季研究発表会ルポ(情報の窓)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- 木の(p, q)-全ラベリング問題
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 順列制約をみたす模調要求をもつ正モジュラシステムについて
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 無向グラフにおける単調な要求関数を持つ辺連結度増大問題