• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Complexite des homomorphismes de graphes avec listes.
【24h】

Complexite des homomorphismes de graphes avec listes.

机译：具有列表的图的同态的复杂性。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem.;At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed.;Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.;Keywords: Complexity, digraph, list-homomorphism, polymorphism, constraint satisfaction problem..
机译：约束满足问题，包括在尊重一组约束的同时为变量分配值，构成了一大类自然问题。为了研究这些问题的复杂性，可以方便地将它们视为关系结构上的同态问题。当前的一个研究主题是表征同态问题所属的复杂性类别。最终目的是确定将关系结构的代数性质和同态问题的复杂性结合在一起的猜想。首先，本文对产生FO列表同态问题的有向图进行了刻画。结果表明，在伸缩有向图的特殊情况下，猜想得以结合，代数和复杂性得到了证实。随后，我们对图的特性进行了描述，这些图产生了弧一致性可解的列表同态问题。我们介绍了单色多态性的概念，并提出了一种简单的算法，如果目标图每k≥2都接受arity k的单色TSI多态性，则可以解决列表同态性问题；关键字：复杂性，有向图，列表同态性，多态性，约束满足问题。

著录项

  • 作者

    Lemaitre, Adrien.;

  • 作者单位

    Universite de Montreal (Canada).;

  • 授予单位 Universite de Montreal (Canada).;
  • 学科 Mathematics.
  • 学位 Ph.D.
  • 年度 2012
  • 页码 151 p.
  • 总页数 151
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 肿瘤学;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号