<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

CSP duality and trees of bounded pathwidth

descriptionPublicationkeyboard_double_arrow_right Article 01 Jul 2010 Spain Publisher:Elsevier BVJournal:Theoretical Computer Science, volume 411, pages 3,188-3,208 (issn: 0304-3975,

Authors: Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei;

doi: 10.1016/j.tcs.2010.05.016

handle: 10230/36329

CSP duality and trees of bounded pathwidth

- Summary
- Subjects
- External Databases
  (1)
- Metrics

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.

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.

Country

Spain

Related Organizations

Keywords

Datalog, Constraint satisfaction problem, Homomorphism duality, Bounded pathwidth, Polymorphisms, Theoretical Computer Science, Computer Science(all)

2jbj

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	7
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average