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

DOI10.1016/J.ENDM.2015.06.008zbMATH Open1346.05218OpenAlexW2197961740MaRDI QIDQ322186FDOQ322186

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

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

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)

Cites Work

• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On maximal independent sets of vertices in claw-free graphs
• Title not available (Why is that?)
• On finding augmenting graphs
• Finding augmenting chains in extensions of claw-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
• New sufficient conditions for \(\alpha\)-redundant vertices
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A note on \(\alpha\)-redundant vertices in graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs

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)