A Semidefinite Programming Relaxation for the Generalized Stable Set Problem(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we generalize the theory of a convex set relaxation for the maximum weight stable set problem due to Grotschel, Lovasz and Schrijver to the generalized stable set problem. We define a convex set which serves as a relaxation problem, and show that optimizing a linear function over the set can be done in polynomial time. This implies that the generalized stable set problem for perfect bidirected graphs is polynomial time solvable. Moreover, we prove that the convex set is a polytope if and only if the corresponding bidirected graph is perfect. The definition of the convex set is based on a semidefinite programming relaxation of Lovasz and Schrijver for the maximum weight stable set problem, and the equivalent representation using infinitely many convex quadratic inequalities proposed by Fujie and Kojima is particularly important for our proof.
- 社団法人電子情報通信学会の論文
- 2005-05-01
著者
-
Fujie Tetsuya
School Of Business Administration University Of Hyogo
-
Tamura Akihisa
Department Of Mathematics Keio University
-
Tamura Akihisa
Department Of Computer Science And Information Mathematics The University Of Electro-communications
関連論文
- A Semidefinite Programming Relaxation for the Generalized Stable Set Problem(Discrete Mathematics and Its Applications)
- THE GENERALIZED STABLE SET PROBLEM FOR PERFECT BIDIRECTED GRAPHS
- EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
- Efficiently scanning all spanning trees of an undirected graph.
- Matching with partially ordered contracts