Computing with Tangles
Computing with Tangles
复制标题
使用缠结进行计算
DOI：
--
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Pascal Schweitzer
中科院分区：
文献类型：
--
作者：
Martin Grohe;Pascal Schweitzer
罗伯逊和西摩在图小理论的背景下引入了图的缠结。缠结可以被视为描述图的“k-连通分量”（尽管以扭曲的方式）。它们在图小理论中发挥着重要作用。缠结的一个有趣的方面是它们不仅可以为图定义，而且更普遍地可以为任意连接函数（即整数值子模函数和对称集函数）定义。然而，缠结很难用算法来处理。首先，尚不清楚如何表示它们，因为它们是分离的家庭，因此可能呈指数级增长。我们的第一个贡献是一个数据结构，用于表示和访问图形中达到某种固定顺序的所有缠结。使用这个数据结构，我们可以证明一个非常通用的结构定理的算法版本，该定理由 Carmesin、Diestel、Harman 和 Hundertmark（对于图）和 Hundertmark（对于任意连接函数）产生一个规范树分解，其部分对应于最大缠结。 （这可以被视为将图分解为其 3 个连通分量的概括。）
Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph (though in a twisted way). They play an important role in graph minor theory. An interesting aspect of tangles is that they cannot only be defined for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions). However, tangles are difficult to deal with algorithmically. To start with, it is unclear how to represent them, because they are families of separations and as such may be exponentially large. Our first contribution is a data structure for representing and accessing all tangles of a graph up to some fixed order. Using this data structure, we can prove an algorithmic version of a very general structure theorem due to Carmesin, Diestel, Harman and Hundertmark (for graphs) and Hundertmark (for arbitrary connectivity functions) that yields a canonical tree decomposition whose parts correspond to the maximal tangles. (This may be viewed as a generalisation of the decomposition of a graph into its 3-connected components.)
排除拓扑子图的图的结构定理和同构检验
DOI：
10.1145/2213977.2213996
发表时间：
2012
期刊：
影响因子：
--
作者：
M. Grohe;D. Marx
通讯作者：
D. Marx