Information Technology Reference
In-Depth Information
Algorithm 1.
FindClique
(
V
(
G
)
,E
(
G
))
1. Read graph
G
2. Generate set
M
(
v
i
)for
∀v
i
∈ V
(
G
)
3.
for
∀v
i
∈ V
(
G
)
do
4. call
clique(
{v
i
}
,
M
(
v
i
)
,
v
i
)
5.
end for
6.
Function
:
clique(
CLIQUE
,
T
,
v
x
)
7.
for
v
j
∈ T
by the ascending order
do
8. build
triangle neighbor
set
T
(
v
x
)from
v
x
and
v
j
9.
if
T
(
v
x
)
=
∅
then
10.
CLIQUE ← CLIQUE ∪ v
x
11. choose
v
k
with the lowest index from
T
(
v
x
)
12. call
clique(
CLIQUE
,
T
(
v
x
)
,
v
k
)
13.
else
14. according to theorem 1
15.
end if
16.
end for
Fig. 12.2.
Example of Search Trees
we finally find that it is not a maximal clique for that it is just contained in
{
v
0
,v
1
,v
2
,v
3
}
. Similarly, for the branch
{
v
0
}→{
v
0
,v
2
,v
3
}
, and even for the
wholetreerootedwith
{
v
1
}
, all the candidate cliques
{
v
0
,v
2
,v
3
}
and
{
v
1
,v
2
,v
3
}
are contained in
. As a result, these traversing processes contribute
nothing at all. If these candidate maximal cliques could be predicted in advance,
the corresponding tedious searching processes will be prevented from the begin-
ning. Therefore, we come up with a pruning strategy as follows. We first give
each obtained maximal clique a clique number. For example, there are 2 maximal
cliques in Fig.12.1.
{
v
0
,v
1
,v
2
,v
3
}
is given 1. Then this
clique number is attached to every vertex in the same maximal clique already
obtained. Consequently, 0 is assigned to
v
0
,
v
1
,
v
2
and
v
3
. 1 is assigned to
v
2
,
v
3
,
v
4
respectively. As a result, both
v
0
and
v
1
have the clique number
{
v
0
,v
1
,v
2
,v
3
}
is given 0, and
{
v
2
,v
3
,v
4
}
{
0
}
;
v
2
and
v
3
have the clique number
.Forthenexttime
when we have obtained the
triangle neighbor
set
T
(
v
i
) with given vertex
v
j
we
can compare the clique numbers of all the vertices in
T
(
v
i
)withthoseof
v
i
and
v
j
in advance. If they all share the same clique number, we can stop the further
searching process, because all these vertices have ever been in some maximal
clique already obtained before. For instance, when we come to the node
{v
0
,v
2
}
{
0
,
1
}
;
v
4
has the clique number
{
1
}
