Polyhedral Proof of a Characterization of Perfect Bidirected Graphs

スポンサーリンク

概要

• 論文の詳細を見る

• Bidirected graphs which are generalizations of undirected graphs, have three types of edges: (+,+)-edges, (-,-)-edges and (+,-)-edges. Undirected graphs are regarded as bidirected graphs whose edges are all of type (+,+). The notion of perfection of undirected graphs can be naturally ex-tended to bidirected graphs in terms of polytopes. The fact that a bidirected graph is perfect if and only if the undirected graph obtained by replacing all edges to (+,+) is perfect was indepen-dently proved by several researchers. This paper gives a poly-hedral proof of the fact and introduces some new knowledge on perfect bidirected graphs.

• 社団法人電子情報通信学会の論文
• 2003-05-01

著者

• Tamura Akihisa

  Research Institute for Mathematical Sciences, Kyoto University

• Tamura Akihisa

  Research Institute For Mathematical Sciences Kyoto University

• IKEBE Yoshiko

  Department of Management Science, Tokyo University of Science

• Ikebe Yoshiko

  Department Of Management Science Tokyo University Of Science

• TAMURA Akihisa

  Research Institute for Mathematical Science, Kyoto University

関連論文

• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• 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

スポンサーリンク