Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem |
| |
| Authors: | D S Malyshev |
| |
| Institution: | 1.National Research University Higher School of Economics,Nizhnii Novgorod,Russia;2.National Research University Nizhnii Novgorod State University,Nizhnii Novgorod,Russia |
| |
| Abstract: | Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional
constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs
|
èn = 1￥ { G:|V(G)| = n,|E(G)| \leqslant n + Clog2 (n)]} . \bigcup\limits_{n = 1}^\infty {\{ G:|V(G)| = n,|E(G)| \leqslant n + C\log _2 (n)]\} .} |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
