Amb motiu del tancament d'estiu, la validació de documents es reprendrà a partir del 28 d'agost de 2026. Disculpeu les molèsties.
Con motivo del cierre de verano, la validación de documentos se reanudará a partir del 28 de agosto de 2026. Disculpad las molestias
Due to the summer closure, document validation will resume starting August 28, 2026. We apologize for any inconvenience.

Files

568959.pdf (217.28 KB)

Document type

Article

Version

Published version

Publication date

2005-11-10

All rights reserved

Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/139831

Landscape of Solutions in Constraint Satisfaction Problems

Journal Title

Authors

Director/Tutor

Journal ISSN

Volume Title

Related resource

https://doi.org/10.1103/PhysRevLett.95.200202

Abstract

We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.

Subject

Geometria de l'espai, Algorismes

Subject (English)

Solid geometry, Algorithms

Citation

Collections

Articles publicats en revistes (Física de la Matèria Condensada)

Citation

MÉZARD, Marc, PALASSINI, Matteo and RIVOIRE, Olivier. Landscape of Solutions in Constraint Satisfaction Problems. Physical Review Letters. 2005. Vol. 95, num. 20, pags. 200202. ISSN 0031-9007. [consulted: 16 of August of 2026]. Available at: https://hdl.handle.net/2445/139831

Export metadata

JSON - METS

Share record