Perfect (0, ± 1)-matrices and perfect bidirected graphs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)339-356
Number of pages18
JournalTheoretical Computer Science
Issue number2
Publication statusPublished - 2000 Mar 28
Externally publishedYes


  • (0, 1)-polytopes
  • (0, ± 1)-matrices
  • Bidirected graphs
  • Perfectness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Perfect (0, ± 1)-matrices and perfect bidirected graphs'. Together they form a unique fingerprint.

Cite this