Show simple item record

dc.contributor.authorAnsótegui Gil, Carlos José
dc.contributor.authorBéjar Torres, Ramón
dc.contributor.authorFernàndez Camon, César
dc.contributor.authorMateu Piñol, Carles
dc.date.accessioned2013-09-17T15:53:39Z
dc.date.available2013-09-17T15:53:39Z
dc.date.issued2007
dc.identifier.isbn9781577353232
dc.identifier.urihttp://hdl.handle.net/10459.1/46640
dc.description.abstractTractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.ca_ES
dc.language.isoengca_ES
dc.publisherAssociation for the Advancement of Artificial Intelligenceca_ES
dc.relation.isformatofVersió postprint del document publicat a: http://www.aaai.orgca_ES
dc.relation.ispartofProceedings of the twenty-second National Conference on Artificial Intelligence, 2007, p. 161-166ca_ES
dc.rights(c) Association for the Advancement of Artificial Intelligence, 2007ca_ES
dc.subject.otherIntel·ligència artificialca_ES
dc.subject.otherCSP (Llenguatge de programació)ca_ES
dc.titleOn balanced CSPs with high treewidthca_ES
dc.typearticleca_ES
dc.identifier.idgrec011050
dc.type.versionacceptedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record