On the maximum independent set problem in graphs of bounded maximum degree

DOI10.1007/S40306-020-00368-0MaRDI QIDQ778157zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 1 July 2020

Published in Acta Mathematica Vietnamica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s40306-020-00368-0

zbMATH Keywords

low degree graphmaximum independent setstable set

Mathematics Subject Classification ID

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

Recommendations

• Maximum independent sets in graphs of low degree
• scientific article; zbMATH DE number 1003268
• scientific article; zbMATH DE number 1305487
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Exact Algorithms for Maximum Independent Set

Cites work

• A note on -redundant vertices in graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• scientific article; zbMATH DE number 3438749 (Why is no real title available?)
• Local transformations of graphs preserving independence number
• Lower bounds on the independence number in terms of the degrees
• Maximum independent sets in graphs of low degree
• New sufficient conditions for \(\alpha\)-redundant vertices
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the maximum independent set problem in subclasses of planar graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Reducibility among combinatorial problems
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs

Cited in

(14)

• The maximum independent set problem in subclasses of subcubic graphs
• New properties of maximum independent set problem solution truncation rules or redundant branches
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• Maximum independent sets in graphs of low degree
• scientific article; zbMATH DE number 5842466 (Why is no real title available?)
• A sufficient condition to extend polynomial results for the maximum independent set problem
• The max quasi-independent set Problem
• Constructing concrete hard instances of the maximum independent set problem
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Computing maximum independent set on outerstring graphs and their relatives
• A simple proof that finding a maximal independent set in a graph is in NC
• An exact algorithm for maximum independent set in degree-5 graphs
• An optimal maximal independent set algorithm for bounded-independence graphs

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

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