A CLP Approach for Solving the Maximum Clique Problem: Benefits and Limits

被引：0

作者：

Badica, Amelia ^{[1
]}

badica, Costin ^{[1
]}

Ivanovic, Mirjana ^{[2
]}

Logofatu, Doina ^{[3
]}

机构：

[1] Univ Craiova, Craiova, Romania

[2] Univ Novi Sad, Novi Sad, Serbia

[3] Univ Appl Sci, Frankfurt, Germany

来源：

2017 21ST INTERNATIONAL CONFERENCE ON SYSTEM THEORY, CONTROL AND COMPUTING (ICSTCC) | 2017年

关键词：

maximal clique; logic programming;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Maximal Clique and Maximum Clique are two related and famous computational problems known to be intractable in the most general case. We propose a formulation of the Maximal Clique problem as a Boolean Satisfaction problem. The constraints are then mapped to a Constraint Logic Programming representation. The resulting representation can be input to a Constraint Logic Programming system that can be used in combination with a suitable Branch-and-Bound search strategy to compute the Clique Number and the Maximum Clique of a given undirected graph. We present initial experimental results that we obtained with this approach by utilizing ECLiPSe-CLP as target implementation platform. We also discuss the potential benefits, as well as the limitations, of this approach.

引用

页码：613 / 617

页数：5

共 9 条

[1] [Anonymous], 2010, Artificial Intelligence-Foundations of Computational Agents
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3] Constraint logic programming
Gavanelli M.
Rossi F.
[J]. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, 6125 : 64 - 86
[4] Harvey WD, 1995, INT JOINT CONF ARTIF, P607
[5] What is answer set programming to propositional satisfiability
Lierler, Yuliya
[J]. CONSTRAINTS, 2017, 22 (03) : 307 - 337
[6] Boolean satisfiability from Theoretical hardness to Practical success
Malik, Sharad
Zhang, Lintao
[J]. COMMUNICATIONS OF THE ACM, 2009, 52 (08) : 76 - 82
[7] NIEDERLINSKI A, 2014, GENTLE GUIDE CONSTRA
[8] ECLiPSe - From LP to CLP
Schimpf, Joachim
Shen, Kish
[J]. THEORY AND PRACTICE OF LOGIC PROGRAMMING, 2012, 12 : 127 - 156
[9] A review on algorithms for maximum clique problems
Wu, Qinghua
Hao, Jin-Kao
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (03) : 693 - 709

← 1 →