Information Technology Reference
In-Depth Information
Algorithm 1:
Class-Refinement(N)
Let
v
1
,
v
2
,...
v
t
be the sequence of nodes visited by
U
(
N
,
d
)
, possibly containing duplicate
nodes ;
Follow
U
and
for
each node v
i
do
Store the labels of each edge incident to
v
i
;
Compute the number of 1-classes and store a distinguishing path for each pair of distinct
classes ;
k
:
(
N
,
d
)
2;
repeat
Follow
U
=
and
for
each node v
i
do
for
each edge
(
N
,
d
)
(
v
i
,
w
)
incident to v
i
do
Compute the
(
k
−
1
)
-class of
w
(using the distinguishing paths);
Store the label of
(
v
i
,
w
)
and the index of the (
k
−
1)-class of
w
;
Compute the number of
k
-classes and store a distinguishing path for each pair of
distinct
k
-classes ;
Increment
k
;
until
the number of k-classes is equal to the number of
(
k
−
)
-classes
;
1
Move to a vertex of class one;
C
.
Y
C
,
C
is accepted from each node
u
∈
C
and it is not accepted from any node
v
∈
C
, either there exists a
C
)
Given any two distinct
k
-classes
C
,
(
C
,
-
distinguishing
C
,
path
of length at most
k
, or there exists a
(
C
)
-
distinguishing path
of length at
most
k
.
For
k
1, it is easy to determine the
k
-class of any node
v
by traversing each
edge incident to
v
and noting the labels. From this information, one can find the
distinguishing paths for any pair of 1-classes. For
k
=
≥
2, it is possible to identify the
k
-classes and the corresponding distinguishing paths (from knowledge of the
k
−
1
classes) using the properties below.
Property 1.
For
k
≥
2, two nodes
u
and
v
belong to the same k-class, i.e.
[
u
]
k
=[
v
]
k
,
if and only if (i)
[
u
]
1
=[
v
]
1
and (ii) for each
i
,0
≤
i
≤
deg
G
(
u
)=
deg
G
(
v
)
,the
i
th
neighbor
u
i
of
u
and the
i
th neighbor
v
i
of
v
belong to the same
(
k
−
1
)
-class and
δ
(
u
,
u
i
)=
δ
(
v
,
v
i
)=(
i
,
j
)
,forsome
j
≥
0.
Theorem 6 ([
8
]).
Algorithm
1
builds the quotient graph of any graph of size n
≤
N
n
3
d
n
3
log
n
(
|
(
,
)
|·
)
(
+
|
(
,
)
|
)
in O
U
N
d
moves and requires O
U
N
d
log
d
memory for
each agent.
There exists a UXS for graphs of size at most
N
and maximum degree at most
d
,
that is of length
O
N
3
d
2
log
N
[
1
]. Using such a sequence for the traversal gives us
an algorithm of move complexity
O
(
)
N
3
n
3
d
3
log
N
(
)
for solving rendezvous.
12.5.2 Agents Having Little Memory
In the algorithms discussed above, the agent needs to have enough memory to
construct and to remember a map of the graph or a part of it. In this section we
Search WWH ::
Custom Search