Partition Into Triangles on Bounded Degree Graphs

被引：24

作者：

van Rooij, Johan M. M. ^{[1
]}

Niekerk, Marcel E. van Kooten ^{[1
]}

Bodlaender, Hans L. ^{[1
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, NL-3508 TB Utrecht, Netherlands

来源：

THEORY OF COMPUTING SYSTEMS | 2013年 / 52卷 / 04期

关键词：

Algorithms; Exact algorithms; Partition into triangles; Graph algorithms; Bounded degree graphs; Satisfiability; EXACT SATISFIABILITY; EXACT ALGORITHMS; NUMBER;

D O I：

10.1007/s00224-012-9412-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 -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 time and linear space.

引用

页码：687 / 718

页数：32

共 24 条

[11] Which problems have strongly exponential complexity?
Impagliazzo, R
Paturi, R
Zane, F
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 63 (04) : 512 - 530
[12] On the complexity of k-SAT
Impagliazzo, R
Paturi, R
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 62 (02) : 367 - 375
[13] MAXIMUM BOUNDED 3-DIMENSIONAL MATCHING IS MAX SNP-COMPLETE
KANN, V
[J]. INFORMATION PROCESSING LETTERS, 1991, 37 (01) : 27 - 35
[14] Koivisto M, 2009, LECT NOTES COMPUT SC, V5917, P258, DOI 10.1007/978-3-642-11269-0_21
[15] Kulikov AS, 2002, J MATH SCI, V293, P118
[16] Kullmann O., 1997, TECHNICAL REPORT
[17] Lipton R.J, 2009, FAST EXPONENTIAL ALG
[18] An algorithm for Exact Satisfiability analysed with the number of clauses as parameter
Madsen, BA
[J]. INFORMATION PROCESSING LETTERS, 2006, 97 (01) : 28 - 30
[19] Monien B., 1981, Methods of Operations Research, P419
[20] Porschen S, 2005, ANN MATH ARTIF INTEL, V43, P173, DOI 10.1007/s10472-005-0428-2

← 1 2 3 →