局所完全ダイグラフの独立双方向支配集合問題について
スポンサーリンク
概要
- 論文の詳細を見る
ダイグラフ D に対して,頂点の部分集合 S が,任意の頂点 u ? S に対して, vu,uw が D の弧であるような v,w ∈ S が存在するという条件を満たすとき, S を D の双方向支配集合という.また双方向支配集合 S のどの 2 頂点も隣接しないとき, S は独立であるという.すべてのダイグラフが独立双方向支配集合を持つとは限らない.本報告では,与えられたダイグラフに独立双方向支配集合が存在するかどうかを判定する問題が NP 完全であることを示す.また,ダイグラフを局所完全ダイグラフと呼ばれるクラスに限定すると,最小の独立双方向支配集合が多項式時間で計算できることを示す.
- 2012-10-26
著者
関連論文
- k木における完全独立全域木について
- k木における完全独立全域木について
- とびらの言葉
- Bipartite permutation graphのL(2,1)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
- 局所完全ダイグラフの独立双方向支配集合問題について
- 完全独立全域木の十分条件について
- A-004 区間グラフの向き付けにおける双方向支配(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
- 完全独立全域木の十分条件について