直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
グラフGの支配集合Dは,Dが誘導する部分グラフが完全マッチングを持つとき,ペア支配集合であるという.ペア支配集合はHaynes, Slaterによって導入され,さらに一般のグラフに対して最小のペア支配集合を求める問題はNP-Hardであることが証明された.本論文では,直並列グラフの最小ペア支配集合を求める線形時間アルゴリズムを提案する.
- 一般社団法人情報処理学会の論文
- 2007-05-11
著者
関連論文
- k木における完全独立全域木について
- k木における完全独立全域木について
- とびらの言葉
- 辺に故障のあるバブルソートグラフのhamiltonian laceability
- バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
- ハイパーキューブ族のネットワークにおける適応型故障診断について
- Bipartite permutation graphのL(2,1)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
- 局所完全ダイグラフの独立双方向支配集合問題について
- 完全独立全域木の十分条件について
- A-004 区間グラフの向き付けにおける双方向支配(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
- 完全独立全域木の十分条件について