The maximum independent set problem in subclasses of subcubic graphs

DOI10.1016/J.DISC.2015.01.041MaRDI QIDQ2346341zbMATH OpenOpenAlexFDO

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

Publication date 1 June 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2015.01.041

zbMATH Keywords

augmenting graphgraph reductionindependence numbermaximum independent setsubcubic graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• On the maximum independent set problem in subclasses of planar graphs
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• The maximum independent set problem for cubic planar graphs
• Independent sets and matchings in subcubic graphs
• On the maximum independent set problem in graphs of bounded maximum degree

Cites work

• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• scientific article; zbMATH DE number 2246590 (Why is no real title available?)
• Maximum independent sets in graphs of low degree
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On maximal independent sets of vertices in claw-free graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• Stability in circular arc graphs
• Stability preserving transformations of graphs
• Struction revisited

Cited in

(15)

• Computational complexity of the vertex cover problem in the class of planar triangulations
• Algorithm to find a maximum 2-packing set in a cactus
• On the maximum independent set problem in subclasses of subcubic graphs
• Maximum independent sets near the upper bound
• An efficient local search framework for the minimum weighted vertex cover problem
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• Independent sets in graphs without subtrees with many leaves
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Independent sets and matchings in subcubic graphs
• Ultimate greedy approximation of independent sets in subcubic graphs
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Weighted independent sets in a subclass of P₆-free graphs

This page was built for publication: 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 Q2346341)