A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
スポンサーリンク
概要
- 論文の詳細を見る
The maximum weight/cardinality stable set problem is to find a maximum weight/cardinality stable set of a given graph. It is well known that these problems for general graphs belong to the class of NP-hard. However, for several classes of graphs, e.g., for perfect graphs and claw-free graphs and so on, these problems can be solved in polynomial time. For instance, Minty (1980), Sbihi (1980) and Lovasz and Plummer (1986) have proposed polynomial time algorithm finding a maximum cardinality stable set of a claw-free graph. Moreover, it has been believed that Minty's algorithm is the unique polynomial time algorithms finding a maximum weight stable set of a daw-free graph up to date. Here we show that Minty's algorithm for the weighted version fails for some special cases, and give modifications to overcome it.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
田村 明久
慶應義塾大学
-
Nakamura Daishin
Department of Mathematical Sciences Tokyo Denki University
-
Tamura Akihisa
Research Institute for Mathematical Sciences, Kyoto University
-
Tamura Akihisa
Research Institute For Mathematical Sciences Kyoto University
-
TAMURA Akihisa
Research Institute for Mathematical Science, Kyoto University
関連論文
- 1-F-10 Existence of sports schedules with multiple venues
- パーフェクト双向グラフ(グラフ・ネットワーク(3))
- On the Local Face Structure of 0-1 Polytopes Related to a Class of Combinatorial Optimizaiton Problems
- Adjacency of the Best and Second Best Valued Solutions in Combinatorial Optimization Problems
- Algorithms for Finding a Kth Best Valued Assignment
- A Recursive Algorithm for a Class of Convex Min-Max Problems
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- A LINEAR TIME ALGORITHM FOR THE GENERALIZED STABLE SET PROBLEM ON TRIANGULATED BIDIRECTED GRAPHS
- 確率モデルにおける最適化研究部会終了報告(ペーパーフェア)
- 制限付き安定部屋割問題とミニマックス安定部屋割問題(組合せ・グラフ・ネットワーク)
- The Rooted Tree Embedding Problem
- A property of the divorce digraph for a stable marriage
- マッチングモデルと離散凸解析を用いたその拡張 : アルゴリズムの観点から(セッション2)
- マッチングモデル(モデリング-最適化モデリング-)
- Application of M-Convex Submodular Flow Problem to Mathematical Economics
- The Linear Complementarity Problem on Oriented Matroids(Special Issue on Algorithm Engineering : Surveys)
- Applications of Discrete Convex Analysis to Mathematical Economics
- Polyhedral Proof of a Characterization of Perfect Bidirected Graphs
- 第22回FMESシンポジウム「デジタル・エンジニアリングと経営工学」(情報の窓)
- 安定結婚からサプライチェーンネットワークの安定性へ(離散凸解析)
- 2-B-4 サプライチェーンネットワークの安定性(離散最適化(5))