| dc.contributor.author | Carvalho, Catarina | |
| dc.contributor.author | Dalmau, Víctor | |
| dc.contributor.author | Krokhin, Andrei | |
| dc.date.accessioned | 2013-01-14T14:29:04Z | |
| dc.date.available | 2013-01-14T14:29:04Z | |
| dc.date.issued | 2010 | |
| dc.identifier.citation | Carvalho , C , Dalmau , V & Krokhin , A 2010 , ' CSP duality and trees of bounded pathwidth ' , Theoretical Computer Science , vol. 411 , no. 34-36 , pp. 3188-3208 . https://doi.org/10.1016/j.tcs.2010.05.016 | |
| dc.identifier.issn | 0304-3975 | |
| dc.identifier.other | PURE: 775030 | |
| dc.identifier.other | PURE UUID: 037b458e-fbab-4a48-984b-8e2cf7baa85e | |
| dc.identifier.other | Scopus: 77955413153 | |
| dc.identifier.other | ORCID: /0000-0002-4648-7016/work/62748321 | |
| dc.identifier.uri | http://hdl.handle.net/2299/9618 | |
| 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.language.iso | eng | |
| dc.relation.ispartof | Theoretical Computer Science | |
| dc.title | CSP duality and trees of bounded pathwidth | en |
| dc.contributor.institution | Mathematics and Theoretical Physics | |
| dc.contributor.institution | Centre for Computer Science and Informatics Research | |
| dc.contributor.institution | School of Physics, Engineering & Computer Science | |
| dc.contributor.institution | Department of Physics, Astronomy and Mathematics | |
| dc.description.status | Peer reviewed | |
| rioxxterms.version | AM | |
| rioxxterms.versionofrecord | https://doi.org/10.1016/j.tcs.2010.05.016 | |
| rioxxterms.type | Journal Article/Review | |
| herts.preservation.rarelyaccessed | true | |
