Partition Into Triangles on Bounded Degree Graphs

被引：25

作者：

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 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Beigel R., 1999, P 10 ACM SIAM S DISC, P856

[3] Exact algorithms for exact satisfiability and number of perfect matchings [J].

Bjorklund, Andreas ;

Husfeldt, Thore .

ALGORITHMICA, 2008, 52 (02) :226-249

[4] EXACT COVERS VIA DETERMINANTS [J].

Bjorklund, Andreas .

27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 :95-106

[5] SET PARTITIONING VIA INCLUSION-EXCLUSION [J].

Bjorklund, Andreas ;

Husfeldt, Thore ;

Koivisto, Mikko .

SIAM JOURNAL ON COMPUTING, 2009, 39 (02) :546-563

[6] Fast Algorithms for max independent set [J].

Bourgeois, Nicolas ;

Escoffier, Bruno ;

Paschos, Vangelis T. ;

van Rooij, Johan M. M. .

ALGORITHMICA, 2012, 62 (1-2) :382-415

[7] New algorithms for Exact Satisfiability [J].

Byskov, JM ;

Madsen, BA ;

Skjernaa, B .

THEORETICAL COMPUTER SCIENCE, 2005, 332 (1-3) :515-541

[8] Algorithms for four variants of the exact satisfiability problem [J].

Dahllöf, V ;

Jonsson, P ;

Beigel, R .

THEORETICAL COMPUTER SCIENCE, 2004, 320 (2-3) :373-394

[9] Faster exact solutions for some NP-hard problems [J].

Drori, L ;

Peleg, D .

THEORETICAL COMPUTER SCIENCE, 2002, 287 (02) :473-499

[10]

Fomin FV, 2010, TEXTS THEOR COMPUT S, P1, DOI 10.1007/978-3-642-16533-7_1

← 1 2 3 →