On the maximum independent set problem in graphs of bounded maximum degree
From MaRDI portal
Publication:778157
DOI10.1007/S40306-020-00368-0zbMATH Open1442.05164OpenAlexW3036520051MaRDI QIDQ778157FDOQ778157
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
Recommendations
Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)
Cites Work
- Reducibility among combinatorial problems
- Lower bounds on the independence number in terms of the degrees
- The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
- Title not available (Why is that?)
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- New sufficient conditions for \(\alpha\)-redundant vertices
- A note on \(\alpha\)-redundant vertices in graphs
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Maximum independent sets in graphs of low degree
- On the maximum independent set problem in subclasses of subcubic graphs
- On the maximum independent set problem in subclasses of planar graphs
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Local transformations of graphs preserving independence number
Cited In (14)
- A simple proof that finding a maximal independent set in a graph is in NC
- An optimal maximal independent set algorithm for bounded-independence graphs
- An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
- New properties of maximum independent set problem solution truncation rules or redundant branches
- Constructing concrete hard instances of the maximum independent set problem
- Maximum independent sets in graphs of low degree
- Further Improvement on Maximum Independent Set in Degree-4 Graphs
- An exact algorithm for maximum independent set in degree-5 graphs
- A sufficient condition to extend polynomial results for the maximum independent set problem
- The maximum independent set problem in subclasses of subcubic graphs
- The max quasi-independent set Problem
- Title not available (Why is that?)
- On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
- Computing maximum independent set on outerstring graphs and their relatives
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)
