2012 | OriginalPaper | Chapter
Algorithms for Some H-Join Decompositions
Authors : Michel Habib, Antoine Mamcarz, Fabien de Montgolfier
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A
homogeneous pair
(also known as a
2-module
) of a graph is a pair {
M
1
,
M
2
} of disjoint vertex subsets such that for every vertex
x
∉ (
M
1
∪
M
2
) and
i
∈ {1,2},
x
is either adjacent to all vertices in
M
i
or to none of them. First used in the context of perfect graphs [Chvátal 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
(
mn
2
)-time algorithm computing (if any) a homogeneous pair, which not only improves a previous bound of
O
(
mn
3
) [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
(
nm
2
)-time algorithm to compute a
N
-join decomposition of a graph, improving a previous
O
(
n
6
) 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.