Decompositions, Tangles, and Clusters

分解、缠结和簇

• 批准号: 414230410
• 负责人: Professor Dr. Martin Grohe
• 金额: --
• 依托单位: Informatik 7 - Lehrstuhl Logik und Theorie diskreter Systeme
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/414230410?language=en
• 关键词: Decompositions; Tangles; Clusters

Tree decompositions, describing how a graph can be cut into largely independent pieces, have become a standard tool in the design of algorithms with applications in many different areas of Computer science. Structural graph theory offers various concepts "dual" to tree decompositions. Intuitively, these can be viewed as describing highly connected regions in graphs. Among them, arguably, tangles are the most important. While far less prominent than tree decompositions, tangles and related concepts such as brambles and well-linked setshave proved useful in several computer science applications, and we feel they have a considerable untapped potential. A largely unexplored idea, first formulated by Diestel and Whittle (2016) in the context of image segmentation, is to use tangles in clustering applications.It is the goal of this proposal to generalise the theory of decompositions and tangles towards new applications in clustering and constraint satisfaction. Technically, this requires an extension of the theory from integer-valued to real-valued connectivity functionsand an extension to new, hybrid decompositions. One important focus of this proposal will be to strengthen the currently underdeveloped algorithmic theory of tangles.

树分解描述了如何将一个图切割成很大程度上独立的部分，已经成为算法设计的标准工具，在计算机科学的许多不同领域都有应用。结构图理论为树分解提供了各种“对偶”概念。直观地说，这些可以被看作是在图中描述高度连接的区域。其中，可以说，缠结是最重要的。虽然远没有树分解那么突出，缠结和相关的概念，如荆棘和良好连接的集合，在几个计算机科学应用中被证明是有用的，我们觉得它们有相当大的未开发的潜力。Diestel和Whittle（2016）首先在图像分割的背景下提出了一个很大程度上未被探索的想法，即在聚类应用中使用缠结。本文的目标是将分解和缠结理论推广到聚类和约束满足的新应用中。从技术上讲，这需要将理论从整数值连接函数扩展到实值连接函数，并扩展到新的混合分解。本提案的一个重要焦点将是加强目前不发达的缠结算法理论。