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

研究成果: Article査読

1 被引用数 (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.

本文言語English
ページ(範囲)339-356
ページ数18
ジャーナルTheoretical Computer Science
235
2
DOI
出版ステータスPublished - 2000 3月 28
外部発表はい

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Perfect (0, ± 1)-matrices and perfect bidirected graphs」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル