点集合間の辺連結度を増大させる問題
スポンサーリンク
概要
- 論文の詳細を見る
グラフG=(V,E),二つの点集合族W_1,W_2⊆2^V-{0},要求関数r:W_1×W_2→R_+が与えられたとき,最小本数の辺を加えることで,W_1∈W_1とW_2∈W_2のすべての組において,W_1からW_2への間の辺連結度をγ(W_1,W_2)以上に増大させる問題を考える.この問題は,辺連結度増大問題,局所辺連結度増大問題,節点領域辺連結度増大問題を特別な場合として含む.本研究では,P=NPでなければ,有向グラフにおける節点領域辺連結度増大問題や無向グラフにおける局所節点領域辺連結度増大問題に限定しても,ある定数cに対し.多項式時間でclog α(W_1,W_2)倍より良い近似ができないことを示す.ただし.α(W_1,W_2)はγ(W_1,W_2)>0であるW_1∈W_1とW_2∈W_2の組の数を表す.一方で,問題がO(log α(W_1,W_2))倍近似可能であることも示す.つまり,P=NPでなければ,問題がΘ(log α(W_1,W_2))倍近似可能であることを示す.さらに,この問題に対し,模調関数を一般化した関数を用いた特徴づけを与える.
- 2008-10-31
著者
関連論文
- 点集合間の辺連結度を増大させる問題
- 平成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)-全ラベリング問題
- 安心・安全社会構築のためのシステム人間科学の創成(テーマ関連/オーガナイズドセッション1)
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 順列制約をみたす模調要求をもつ正モジュラシステムについて
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 無向グラフにおける単調な要求関数を持つ辺連結度増大問題
- ホーン理論の内包・外包に対する演繹推論
- 有限グラフ上のランダムウォークの脱乱択化
- 単調な論理関数の双対化について