The maximum independent set problem in subclasses of S_i, j, k-free graphs

DOI10.1016/J.ENDM.2015.06.008MaRDI QIDQ322186zbMATH OpenOpenAlexFDO

Authors Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer

Publication date 14 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.06.008

zbMATH Keywords

augmenting graphmaximum independent set\(\alpha\)-redundant vertex

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• The maximum independent set problem in subclasses of subcubic graphs
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the maximum independent set problem in subclasses of planar graphs

Cites work

• scientific article; zbMATH DE number 2246590 (Why is no real title available?)
• A note on \(\alpha\)-redundant vertices in graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Finding augmenting chains in extensions of claw-free graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• New sufficient conditions for \(\alpha\)-redundant vertices
• On finding augmenting graphs
• On maximal independent sets of vertices in claw-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem

Cited in

(11)

• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Augmenting approach for some maximum set problems
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On generalizations of the shadow independent set problem
• The maximum independent set problem in subclasses of subcubic graphs
• On the maximum independent set problem in graphs of bounded maximum degree
• Parameterized complexity of independent set in H-free graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the maximum independent set problem in subclasses of planar graphs
• Independent Sets in Classes Related to Chair-Free Graphs
• Parameterized complexity of independent set in \(H\)-free graphs

This page was built for publication: The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs

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