Algorithms for Some H-Join Decompositions
Algorithms for Some H-Join Decompositions
复制标题
一些 H-Join 分解的算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
F. D. Montgolfier
中科院分区：
文献类型：
--
作者：
M. Habib;Antoine Mamcarz;F. D. Montgolfier
图的齐次对（也称为2-模）是一对{M1，M2}不相交的顶点子集，使得对于每个顶点x <$（M1 <$M2）且i∈{1，2}，x要么与Mi中的所有顶点相邻，要么不与任何顶点相邻。它首先用于完美图的上下文中[Chvatal和Sbihi 1987]，它是分裂（也称为1-连接）和模的推广。计算它们的算法似乎相当复杂。在本文中，我们描述了一个O（mn 2）时间算法计算（如果有的话）一个同质对，它不仅改善了以前的O（mn 3）界[埃弗雷特，克莱因和里德1997]，但也使用了一个很好的结构性质同质对。我们的结果可以推广到计算整个齐次对分解树，在相同的复杂度。使用类似的思想，我们提出了一个O（nm 2）时间算法来计算图的N-join分解，改进了以前的O（n6）算法[Feder et al. 2005]。这两个分解是H连接的特殊情况[Bui-Xuan，Telle和Vatshelle 2010]，我们的技术适用于此。
A homogeneous pair (also known as a 2-module) of a graph is a pair {M1, M2} of disjoint vertex subsets such that for every vertex x∉(M1∪M2) and i∈{1,2}, x is either adjacent to all vertices in Mi or to none of them. First used in the context of perfect graphs [Chvatal and Sbihi 1987], it is a generalization of splits (a.k.a 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn2)-time algorithm computing (if any) a homogeneous pair, which not only improves a previous bound of O(mn3) [Everett, Klein and Reed 1997], but also uses a nice structural property of homogenous pairs. Our result can be extended to compute the whole homogeneous pair decomposition tree, within the same complexity. Using similar ideas, we present an O(nm2)-time algorithm to compute a N-join decomposition of a graph, improving a previous O(n6) algorithm [Feder et al. 2005]. These two decompositions are special case of H-joins [Bui-Xuan, Telle and Vatshelle 2010] to which our techniques apply.