CSP duality and trees of bounded pathwidth
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Carvalho, Catarina
- dc.contributor.author Dalmau, Víctor
- dc.contributor.author Krokhin, Andrei
- dc.date.accessioned 2019-01-18T11:13:08Z
- dc.date.available 2019-01-18T11:13:08Z
- dc.date.issued 2010
- dc.description.abstract We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game.en
- dc.description.sponsorship The first author is supported by FCT grant SFRH/BPD/26216/2006 and also by FCT and FEDER within the project ISFL-1-143 of the Centre for Algebra of the University of Lisbon. The second author is supported by grants TIN2006-15387-C03-03 and TIN2007-68005-C04 funded by the MCyT. The third author is supported by the UK EPSRC grants EP/G011001/1 and EP/C543831/1.
- dc.format.mimetype application/pdf
- dc.identifier.citation Carvalho C, Dalmau V, Krokhin A. CSP duality and trees of bounded pathwidth. Theor Comput Sci. 2010 Jul 17;411(34-36):3188-208. DOI: 10.1016/j.tcs.2010.05.016
- dc.identifier.doi http://dx.doi.org/10.1016/j.tcs.2010.05.016
- dc.identifier.issn 0304-3975
- dc.identifier.uri http://hdl.handle.net/10230/36329
- dc.language.iso eng
- dc.publisher Elsevier
- dc.relation.ispartof Theoretical Computer Science. 2010 Jul 17;411(34-36):3188-208.
- dc.relation.projectID info:eu-repo/grantAgreement/ES/2PN/TIN2006-15387-C03-03
- dc.relation.projectID info:eu-repo/grantAgreement/ES/2PN/TIN2007-68005-C04
- dc.rights © Elsevier http://dx.doi.org/10.1016/j.tcs.2010.05.016
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Constraint satisfaction problem
- dc.subject.keyword Homomorphism duality
- dc.subject.keyword Datalog
- dc.subject.keyword Polymorphisms
- dc.subject.keyword Bounded pathwidth
- dc.title CSP duality and trees of bounded pathwidth
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion