加载中…
2018-10-25
Maximum Independent Sets in Subcubic Graphs: New Results
Ararat HarutyunyanMichael LampisVadim LozinJérôme Monnot
文献摘要
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本