Space-efficient Planar Acyclicity Constraints - A Declarative Pearl

Taus Brock-Nannestad 1
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Many constraints on graphs, e.g. the existence of a simple path between two vertices, or the connectedness of the subgraph induced by some selection of vertices, can be straightforwardly represented by means of a suitable acyclicity constraint. One method for encoding such a constraint in terms of simple, local constraints uses a 3-valued variable for each edge, and an (N+1)-valued variable for each vertex, where N is the number of vertices in the entire graph. For graphs with many vertices, this can be somewhat inefficient in terms of space usage. In this paper, we show how to refine this encoding into one that uses only a single bit of information, i.e. a 2-valued variable, per vertex, assuming the graph in question is planar. We furthermore show how this same constraint can be used to encode connectedness constraints, and a variety of other graph-related constraints.
Type de document :
Communication dans un congrès
FLOPS 2016 - 13th International Symposium on Functional and Logic Programming, Mar 2016, Kochi, Japan
Liste complète des métadonnées

https://hal.inria.fr/hal-01426753
Contributeur : Taus Brock-Nannestad <>
Soumis le : mercredi 4 janvier 2017 - 19:24:03
Dernière modification le : jeudi 12 avril 2018 - 01:46:59
Document(s) archivé(s) le : mercredi 5 avril 2017 - 15:23:35

Fichier

flops16acyclicity.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

  • HAL Id : hal-01426753, version 1

Collections

Citation

Taus Brock-Nannestad. Space-efficient Planar Acyclicity Constraints - A Declarative Pearl. FLOPS 2016 - 13th International Symposium on Functional and Logic Programming, Mar 2016, Kochi, Japan. 〈hal-01426753〉

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

20