THE GENERALIZED STABLE SET PROBLEM FOR PERFECT BIDIRECTED GRAPHS

スポンサーリンク

概要

• 論文の詳細を見る

• Bidirected graphs are a generalization of undirected graphs. For bidirected graphs, we can consider a problem which is a natural extension of the maximum weighted stable set problem for undirected graphs. Here we call this problem the generalized stable set problem. It is well known that the maximum weighted stable set problem is solvable in polynomial time for perfect undirected graphs. Perfectness is naturally extended to bidirected graphs in terms of polytopes. Furthermore, it has been proved that a bidirected graph is perfect if and only if its underlying graph is perfect. Thus it is natural to expect that the generalized stable set problem for perfect bidirected graphs can be solved in polynomial time. In this paper, we show that the problem for any bidirected graph is reducible to the maximum weighted stable set problem for a certain undirected graph is in time polynomial in the number of vertices, and moreover, prove that this reduction preserves perfectness. That is, this paper gives an affirmative answer to our expectation.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Tamura Akihisa

  Department Of Mathematics Keio University

• Tamura Akihisa

  Department Of Computer Science And Information Mathematics University Of Electro-communications

• 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

スポンサーリンク