[HTML][HTML] P5-free augmenting graphs and the maximum stable set problem
The complexity status of the maximum stable set problem in the class of P5-free graphs is
unknown. In this paper, we first propose a characterization of all connected P5-free
augmenting graphs. We then use this characterization to detect families of subclasses of P5-
free graphs where the maximum stable set problem has a polynomial time solution. These
families extend several previously studied classes.
unknown. In this paper, we first propose a characterization of all connected P5-free
augmenting graphs. We then use this characterization to detect families of subclasses of P5-
free graphs where the maximum stable set problem has a polynomial time solution. These
families extend several previously studied classes.
The complexity status of the maximum stable set problem in the class of P5-free graphs is unknown. In this paper, we first propose a characterization of all connected P5-free augmenting graphs. We then use this characterization to detect families of subclasses of P5-free graphs where the maximum stable set problem has a polynomial time solution. These families extend several previously studied classes.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果