On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs

DOI10.1007/978-3-642-45278-9_27MaRDI QIDQ2870037zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot, Bernard Ries, Vadim 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

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

Recommendations

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

Cited in

(14)

• On the maximum independent set problem in subclasses of subcubic 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
• Independent Sets in Classes Related to Chair-Free Graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• On the maximum independent set problem in subclasses of planar 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
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite 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

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