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