License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2017.5
URN: urn:nbn:de:0030-drops-84559
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8455/
Go to the corresponding OASIcs Volume Portal

Codish, Michael ; Frank, Michael ; Metodi, Amit ; Muslimany, Morad

Logic Programming with Max-Clique and its Application to Graph Coloring (Tool Description)

pdf-format:
OASIcs-ICLP-2017-5.pdf (0.5 MB)

Abstract

This paper presents pl-cliquer, a Prolog interface to the
cliquer tool for the maximum clique problem.

Using pl-cliquer facilitates a programming style that allows logic programs to integrate with other tools such as: Boolean
satisfiability solvers, finite domain constraint solvers, and graph isomorphism tools.

We illustrate this programming style to solve the Graph Coloring problem, applying a symmetry break that derives from finding a maximum clique in the input graph.

We present an experimentation of the resulting Graph Coloring solver on two benchmarks, one from the graph coloring community and the other from the examination timetabling community.

The implementation of pl-cliquer consists of two components: A lightweight C interface, connecting cliquer's C library and
Prolog, and a Prolog module which loads the library.
The complete tool is available as a SWI-Prolog module.

BibTeX - Entry

@InProceedings{codish_et_al:OASIcs:2018:8455,
  author =	{Michael Codish and Michael Frank and Amit Metodi and Morad Muslimany},
  title =	{{Logic Programming with Max-Clique and its Application to Graph Coloring (Tool Description)}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{5:1--5:18},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Ricardo Rocha and Tran Cao Son and Christopher Mears and Neda Saeedloei},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8455},
  URN =		{urn:nbn:de:0030-drops-84559},
  doi =		{10.4230/OASIcs.ICLP.2017.5},
  annote =	{Keywords: Logic Programming, Constraints, Maximum Clique}
}

Keywords: Logic Programming, Constraints, Maximum Clique
Collection: Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)
Issue Date: 2018
Date of publication: 14.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI