On the maximum independent set problem in subclasses of subcubic graphs
DOI10.1016/J.JDA.2014.08.005zbMATH Open1325.05129OpenAlexW2140079855MaRDI QIDQ2018543FDOQ2018543
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Approximation algorithms for NP-complete problems on planar graphs
- Independent set in \(P_5\)-free graphs in polynomial time
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On maximal independent sets of vertices in claw-free graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- Graphs without large apples and the maximum weight independent set problem
- Computing independent sets in graphs with large girth
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
- Title not available (Why is that?)
- 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
- 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
- Weighted independent sets in a subclass of \(P_6\)-free 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)
