Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Linear-Time Enumeration of Isolated Cliques
verfasst von : Hiro Ito, Kazuo Iwama, Tsuyoshi Osumi
Erschienen in: Algorithms – ESA 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For a given graph
G
of
n
vertices and
m
edges, a clique
S
of size
k
is said to be
c
-isolated if there are at most
ck
outgoing edges from
S
. It is shown that this parameter
c
is an interesting measure which governs the complexity of finding cliques. In particular, if
c
is a constant, then we can enumerate all
c
-isolated maximal cliques in linear time, and if
c
=
O
(log
n
), then we can enumerate all
c
-isolated maximal cliques in polynomial time. Note that there is a graph which has a superlinear number of
c
-isolated cliques if
c
is not a constant, and there is a graph which has a superpolynomial number of
c
-isolated cliques if
c
=
ω
(log
n
). In this sense our algorithm is optimal for the linear-time and polynomial-time enumeration of
c
-isolated cliques.