Information Technology Reference
In-Depth Information
each of size
q
such that the vertices in thesameclassaresym-
metric and indistinguishable from each other. This is also related to the concept of
views introduced in [
24
]. Nodes having the same view belong to the same equiva-
lence class.
=
|
V
(
G
)
|/|
V
(
H
)
|
Definition 3.
Given a labeled graph
(
G
,
λ
)
with a port numbering
δ
,the
view
of a
node
v
is the infinite rooted tree denoted by
T
G
(
v
)
defined as follows. The root of
T
G
(
v
)
represents the node
v
and for each neighbor
u
i
of
v
, there is a vertex
x
i
in
T
G
(
v
)
(labeled by
λ
(
u
i
)
) and an edge from the root to
x
i
with the same labels as the edge
from
v
to
u
i
in
(
G
,
δ
)
. The subtree of
T
G
(
v
)
rooted at
x
i
is again the view
T
G
(
u
i
)
of
node
u
i
.
For traversal of an unknown graph we will use the notion of a
Universal Explo-
ration Sequence
(UXS) [
20
]. For any node
u
∈
G
,wedefinethe
i
th successor of
u
,
denoted by
succ
(
u
,
i
)
as the node
v
reached by taking port number
i
from node
u
(where 0
be a sequence of integers. An
application
of this sequence to a graph
G
at node
u
is the sequence of nodes
≤
i
<
d
(
u
)
). Let
(
a
1
,
a
2
,...,
a
k
)
(
u
0
,...,
u
k
+
1
)
ob-
tained as follows:
u
0
=
u
,
u
1
=
succ
(
u
0
,
0
)
;forany1
≤
i
≤
k
,
u
i
+
1
=
succ
(
u
i
,
(
p
+
a
i
)
mod
d
(
u
i
))
,where
p
is the port-number at
u
i
corresponding to the edge
{
u
i
−
1
,
u
i
}
.
A sequence
whose application to a graph
G
at any node
u
contains
all nodes of this graph is called a UXS for this graph. A UXS for a class of graphs is
a UXS for all graphs in this class. For any positive integers
n
(
a
1
,
a
2
,...,
a
k
)
,
d
,
d
<
n
, there exists
n
3
d
2
log
n
(
)
a UXS of length
O
for the family of all graphs with at most
n
nodes and
maximum degree at most
d
[
1
].
12.3 Feasibility of Deterministic Rendezvous
Deterministic rendezvous is not always possible in arbitrary graphs, as we have seen
before (recall the example of the two agents symmetrically placed in a ring). Given
an environment
(
G
,
λ
,Q,
p
,
δ
)
, the feasibility of rendezvous may depend on the
structure of
G
, the labeling
as well as the initial place-
ment of the agents. When the agents do not have the capability of marking nodes,
the feasibility of rendezvous depends on the labeled graph
λ
, the port numbering
δ
and not on the
starting locations. This is equivalent to the feasibility of electing a leader among the
nodes of a graph, a well-studied problem for which there exists a known characteri-
zation of solvable instances. The following properties are based on the results from
[
5
,
24
,
25
].
(
G
,
λ
,
δ
)
Theorem 1.
Rendezvous is solvable in
(
G
,
λ
,
δ
)
irrespective of the number of agents
and their starting locations if and only if
is symmetric-covering-minimal
with respect to any covering projection that preserves the edge-labeling
(
G
,
λ
,
δ
)
δ
and the
node-labeling
λ
.
On the other hand, if the agents are allowed to mark the nodes of the graph then
the placement
p
of the agents in
G
influences the solvability of rendezvous. In this
Search WWH ::
Custom Search