Maximum independent sets in subcubic graphs: new results

DOI10.1016/j.tcs.2020.09.010zbMath1464.68285arXiv1810.10940OpenAlexW4205377351MaRDI QIDQ5919020

Vadim V. Lozin, Jérôme Monnot, Michael Lampis, Ararat Harutyunyan

Publication date: 6 November 2020

Published in: Theoretical Computer Science, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.10940

zbMATH Keywords

independent setpolynomial algorithmmaximum independent setsubcubic graphapple-free graphssub-cubic graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

In memory of Jérôme Monnot, Maximum independent sets in subcubic graphs: new results

Cites Work

• Graphs without large apples and the maximum weight independent set problem
• Decomposition by clique separators
• On maximal independent sets of vertices in claw-free graphs
• An algorithm for finding clique cut-sets
• Computing independent sets in graphs with large girth
• Treewidth for graphs with small chordality
• Struction revisited
• On the maximum independent set problem in subclasses of subcubic graphs
• From matchings to independent sets
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Maximum independent sets in subcubic graphs: new results