On the maximum independent set problem in subclasses of subcubic graphs

DOI10.1016/j.jda.2014.08.005zbMath1325.05129OpenAlexW2140079855MaRDI QIDQ2018543

Jérôme Monnot, Bernard Ries, Vadim V. Lozin

Publication date: 24 March 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.08.005

zbMATH Keywords

independent setpolynomial-time algorithmsubcubic graphAPX-completeness

Mathematics Subject Classification ID

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

Related Items (12)

New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Boundary classes for graph problems involving non-local properties ⋮ A method of graph reduction and its applications ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs ⋮ Unnamed Item ⋮ Critical hereditary graph classes: a survey ⋮ Maximum independent sets in subcubic graphs: new results ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ On the maximum independent set problem in graphs of bounded maximum degree

Cites Work

• Unnamed Item
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Graphs without large apples and the maximum weight independent set problem
• On maximal independent sets of vertices in claw-free graphs
• Computing independent sets in graphs with large girth
• Optimization, approximation, and complexity classes
• Approximation algorithms for NP-complete problems on planar graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: On the maximum independent set problem in subclasses of subcubic graphs