パーフェクト双向グラフに対する一般化安定集合問題とその多項式時間解法
スポンサーリンク
概要
- 論文の詳細を見る
双向グラフは無向グラフを一般化したもので、各辺はさらに両端点に正または負の符号を持っている。ここでは、無向グラフに対する最大重み安定集合問題を双向グラフに一般化した問題を扱う。この問題を一般化安定集合問題と呼ぶことにする。最大重み安定集合問題は、無向グラフがパーフェクトならば多項式時間で解けることが知られている。一方、パーフェクトという概念は双向グラフにも自然に拡張される。また、双向グラフがパーフェクトである必要十分条件は各辺を無向辺で置き換えて得られる無向グラフがパーフェクトとなることが示されている。本論文では、一般化安定集合問題が最大重み安定集合問題に帰着され、この帰着がパーフェクト性を保存することを示すことで、パーフェクト双向グラフに対するこの問題が多項式時間で解けることを示す。
- 一般社団法人情報処理学会の論文
- 1997-03-14
著者
関連論文
- パーフェクト双向グラフ(グラフ・ネットワーク(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シンポジウムルポ