Biology Reference
In-Depth Information
one is interested in the lattice structure of all concepts; in DM, one is often inter-
ested in computing frequent closed itemsets only.
Time complexity.
Given a bipartite graph, it is not difficult to see that there can
be exponentially many maximal bipartite cliques. For problems with potentially
exponential (in the size of the input) size output, in their seminal paper [14], John-
son et al introduced several notions of
polynomial time
for algorithms for these
problems:
polynomial total time
,
incremental polynomial time
,
polynomial de-
lay time
. An algorithm runs in polynomial total time if the time is bounded by
a polynomial in the size of the input and the size of the output. An algorithm
runs in incremental polynomial time if the time required to generate a succes-
sive output is bounded by the size of input and the size of output generated thus
far. An algorithm runs in polynomial delay time if the generation of each output
is only polynomial in the size of input. It is not difficult to see that polynomial
delay is stronger than incremental polynomial (namely an algorithm with polyno-
mial delay time is also running in incremental polynomial), which is stronger than
polynomial total time. polynomial delay algorithm, we can further distinguish if
the space used is polynomial or exponential in the input size.
Previous work.
Observe that the maximal bipartite clique (MBC) problem is a
special case of the maximal clique problem in a general graph. Namely, given
a bipartite graph
G
=(
V
1
,V
2
,E
), a maximal bipartite clique corresponds to a
maximal clique in
G
=(
V
1
∪
V
2
, E
) where
E
=
E
V
2
).
Consequently, any algorithm for enumerating all maximal cliques in a general
graph [14, 28], also solves the MBC problem. In fact, the best known algorithm
in enumerating all maximal bipartite cliques, which was proposed by Makino and
Uno [20] that takes
O
(∆
2
) polynomial delay time where ∆ is the maximum de-
gree of
G
, was based on this approach. The fact that the set of maximal bipartite
cliques constitutes a lattice was not observed in the paper and thus the property
was not utilized for the enumeration algorithm.
In FCA, much of research has been devoted to study the properties of the lat-
tice structure. There are several algorithms [19, 22, 31], that construct the lattice,
i.e. computing all concepts together with its lattice order. There are also some
algorithms that compute only concepts [13, 21]. (We remark that the idea of using
atotal
lectical order
on concepts Ganter's algorithm [13] is also used for enumer-
ating maximal (bi)cliques.) [14, 20] See [18] for a comparison studies of these
algorithms. The best polynomial total time algorithm was by Nourine and Ray-
naud [22] with
O
(
nm
∪
(
V
1
×
V
1
)
∪
(
V
2
×
|B|
) time and
O
(
n
|B|
) space, where
n
=
|O|
and
m
=
|M|
Search WWH ::
Custom Search