On the maximum independent set problem in subclasses of subcubic graphs

DOI10.1016/J.JDA.2014.08.005MaRDI QIDQ2018543zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Jérôme Monnot, Bernard Ries

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

Graph algorithms (graph-theoretic aspects) (05C85) 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

• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• The maximum independent set problem in subclasses of subcubic graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Approximation algorithms for NP-complete problems on planar graphs
• Computing independent sets in graphs with large girth
• Graphs without large apples and the maximum weight independent set problem
• Independent set in \(P_5\)-free graphs in polynomial time
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Optimization, approximation, and complexity classes

Cited in

(22)

• Independent sets and matchings in subcubic graphs
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• scientific article; zbMATH DE number 7742928 (Why is no real title available?)
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• Some APX-completeness results for cubic graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Boundary classes for graph problems involving non-local properties
• Weighted independent sets in a subclass of P₆-free graphs
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Hamiltonian cycles in subcubic graphs: what makes the problem difficult
• Ultimate greedy approximation of independent sets in subcubic graphs
• Critical hereditary graph classes: a survey
• A method of graph reduction and its applications
• The maximum independent set problem in subclasses of subcubic graphs
• On the maximum independent set problem in graphs of bounded maximum degree
• Independent sets in graphs without subtrees with many leaves
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• On the maximum independent set problem in subclasses of planar graphs

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

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