On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs

DOI10.1007/978-3-642-45278-9_27zbMath1407.68366OpenAlexW2554401705MaRDI QIDQ2870037

Bernard Ries, Jérôme Monnot, Vadim V. Lozin

Publication date: 17 January 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45278-9_27

zbMATH Keywords

independent setpolynomial-time algorithmsubcubic graph

Mathematics Subject Classification ID

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

Related Items (4)

Independent Sets in Classes Related to Chair-Free Graphs ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ The maximum independent set problem in subclasses of subcubic graphs

This page was built for publication: On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs