Stability in \(P_5\)- and banner-free graphs

DOI10.1016/S0377-2217(99)00460-9zbMath0952.90042MaRDI QIDQ1580977

Vadim V. Lozin

Publication date: 14 September 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

stable set; graph theory; polynomial algorithm

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C90: Applications of graph theory

Related Items

A note on \(\alpha\)-redundant vertices in graphs, Augmenting graphs for independent sets, On independent vertex sets in subclasses of apple-free graphs, New applications of clique separator decomposition for the maximum weight stable set problem, On finding augmenting graphs, Maximum independent sets in subclasses of \(P_{5}\)-free graphs, Finding augmenting chains in extensions of claw-free graphs, An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs, 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, Stabex method for extension of \(\alpha\)-polynomial hereditary classes., 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, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stability number of bull- and chair-free graphs
• On semi-\(P_ 4\)-sparse graphs
• On the use of Boolean methods for the computation of the stability number
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Polynomially solvable cases for the maximum stable set problem
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• A New Algorithm for Generating All the Maximal Independent Sets
• Local transformations of graphs preserving independence number