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