クローフリーグラフに対する最大重み安定集合問題とその一般化
スポンサーリンク
概要
- 論文の詳細を見る
一般化安定集合問題は, 無向グラフの最大重み安定集合問題の双向グラフへの拡張である.後者の問題は, クローフリー無向グラフに限定すれば多項式時間で解けることが知られている.本研究では一般化安定集合問題がクローフリー双方グラフに限定すれば多項式時間で解けることを示す.
- 一般社団法人情報処理学会の論文
- 1998-03-20
著者
関連論文
- パーフェクト双向グラフ(グラフ・ネットワーク(3))
- On the Local Face Structure of 0-1 Polytopes Related to a Class of Combinatorial Optimizaiton Problems
- The "branch-and-support" method for the maximum stable set problem
- 今野浩, 松原望編, シリーズ【現代人の数理】, 朝倉書店
- 無向グラフにおける全ての全域木の効率的探索法(グラフ・ネットワーク)
- EP Theorems and Complementarity Problems
- クローフリー双向グラフに対する一般化安定集合問題 (数理最適化の理論と応用)
- クローフリーグラフに対する最大重み安定集合問題とその一般化
- 一般化安定集合問題
- K_1,_3自由グラフの最大重み安定集合を求めるMintyの算法の修正(グラフ理論(3))
- パーフェクト双向グラフに対する一般化安定集合問題とその多項式時間解法(グラフ・ネットワーク(3))
- パーフェクト双向グラフに対する一般化安定集合問題とその多項式時間解法
- 線形計画法と組合せ最適化(トーリック多様体の幾何と凸多面体)
- RAMPシンポジウムルポ
- On the maximum weight stable set problem and its extension for claw-free graphs