Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/2346
Title: | A CLP approach for solving the maximum clique problem: Benefits and limits | Authors: | Badica A. Badica C. Ivanović, Mirjana Logofatu D. |
Issue Date: | 13-Nov-2017 | Journal: | 2017 21st International Conference on System Theory, Control and Computing, ICSTCC 2017 | Abstract: | © 2017 IEEE. 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. | URI: | https://open.uns.ac.rs/handle/123456789/2346 | ISBN: | 9781538638422 | DOI: | 10.1109/ICSTCC.2017.8107103 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
2
checked on May 10, 2024
Page view(s)
11
Last Week
1
1
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.