Abstract | ||
---|---|---|
•We study the parameterized complexity of the γ-complete graph problem.•We prove that the problem is W[1]-hard when 12≤γ<1.•We describe an FPT algorithm for this problem based on color-coding. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.ipl.2021.106105 | Information Processing Letters |
Keywords | DocType | Volume |
γ-Complete graph,Clique relaxations,Graph algorithms,Parameterized complexity | Journal | 169 |
ISSN | Citations | PageRank |
0020-0190 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ambroise Baril | 1 | 0 | 0.34 |
Riccardo Dondi | 2 | 89 | 18.42 |
Mohammad Mehdi Hosseinzadeh | 3 | 0 | 1.01 |