Partition Into Triangles on Bounded Degree Graphs |
| |
Authors: | Johan M. M. van Rooij Marcel E. van Kooten Niekerk Hans L. Bodlaender |
| |
Affiliation: | 1. Department of Information and Computing Sciences, Utrecht University, P. O. Box 80.089, 3508, TB Utrecht, The Netherlands
|
| |
Abstract: | We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes $mathcal{NP}$ -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in $mathcal{O}(1.02220^{n})$ time and linear space. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|