Perfect (0,+/- 1)-matrices and perfect bidirected graphs
Perfect (0, +/-1)-matrices and perfect bidirected graphs are independently defined but are closely related. In this paper, we discuss these relations and give several characterizations of perfectness. The generalized stable set problem associated with bidirected graphs is a generalization of the maximum weighted stable set problem. We also give a brief proof that if a given bidirected graph is perfect, then the problem can be solved in polynomial time. (C) 2000 Elsevier Science B.V. All rights reserved.
perfectness bidirected graphs (0, +/- 1)-matrices (0,1)-polytopes