Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
From MaRDI portal
Publication:290201
DOI10.1016/S0020-0190(96)00197-4zbMath1337.68136MaRDI QIDQ290201
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
05C75: Structural characterization of families of graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A note on \(\alpha\)-redundant vertices in graphs, Augmenting graphs for independent sets, Maximum weight independent sets in hole- and co-chair-free graphs, A note on the computational complexity of graph vertex partition, New applications of clique separator decomposition for the maximum weight stable set problem, Maximum independent sets in subclasses of \(P_{5}\)-free graphs, Finding augmenting chains in extensions of claw-free graphs, Some results on graphs without long induced paths, Stable sets in certain \(P_6\)-free graphs, An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs, On easy and hard hereditary classes of graphs with respect to the independent set problem, Struction revisited, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, \(P_{5}\)-free augmenting graphs and the maximum stable set problem, Stable sets in two subclasses of banner-free graphs, Some results on maximum stable sets in certain \(P_{5}\)-free graphs, Stability in \(P_5\)- and banner-free graphs, On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs, Stability number in subclasses of \(P_5\)-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, On the stable set problem in special \(P_{5}\)-free graphs, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, Augmenting chains in graphs without a skew star.
