Finding augmenting chains in extensions of claw-free graphs

DOI10.1016/S0020-0190(03)00223-0zbMATH Open1162.68412MaRDI QIDQ1007635FDOQ1007635

Authors: Vadim Lozin, Alain Hertz, David Schindl 

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Recommendations

• Augmenting chains in graphs without a skew star.
• On finding augmenting graphs
• Combinatorics and algorithms for augmenting graphs
• scientific article; zbMATH DE number 2246590
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH

zbMATH Keywords

graph algorithmscombinatorial problemspolynomial algorithmsstable setsaugmenting chains

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Cites Work

• Paths, Trees, and Flowers
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On maximal independent sets of vertices in claw-free graphs
• TWO THEOREMS IN GRAPH THEORY
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Stable sets in certain \(P_6\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• On the stable set problem in special \(P_{5}\)-free graphs
• Computing independent sets in graphs with large girth
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Augmenting graphs for independent sets
• Stability in \(P_5\)- and banner-free graphs

Cited In (8)

• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• On finding augmenting graphs
• Augmenting chains in graphs without a skew star.
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Some new hereditary classes where graph coloring remains NP-hard

This page was built for publication: Finding augmenting chains in extensions of claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007635)