Information Technology Reference
In-Depth Information
Partition the set of vertices into
ʲ
equivalence classes
C
0
,
C
1
,...,
C
ʲ
−
1
where
=
∧
n
/ʲ
∩
i
C
j
V
j
+
i
ʲ
. Since the
C
i
s partition the vertex set, we have the following
=
0
fact.
n
j
∅
so that
Fact 10
ʲ
The Partial-BFS algorithm (described below) constructs
C
j
∅
|
C
j
∅
|
level by level.
n
ʲ
Since we do not explicitly know which
C
j
has
nodes, the algorithm will keep
a counter to count the number of vertices and try from
j
=
0. At any point of
n
ʲ
the construction, if
, it will abandon that
j
and try the next value for
j
.
The algorithm will succeed for the first such
j
. This will only increase the space
by an additive
O
|
C
j
|
>
factor and the time by a multiplicative factor of
ʲ
. Hence
we assume that the algorithm knows
j
∅
. Following is the description of the Partial-
BFS algorithm.
(
log
n
)
Partial-BFS
(
G
,
s
)
/* Outputs
C
j
∅
*/
V
0
={
}
V
j
∅
=
Construct
(
s
j
∅
)
,
V
0
,
G
n
ʲ
∩
V
i
ʲ
+
j
∅
=
Construct
(
=
∧
For
i
1to
G
,
V
(
i
−
1
)ʲ
+
j
∅
, ʲ)
Add
V
i
ʲ
+
j
∅
to
C
j
∅
End-For
Output
C
j
∅
In general, the procedure Construct takes
G
and a set of nodes
S
and a parameter
ʲ
and returns the set of nodes that are at distance
ʲ
from some node in
S
. Construct
will use the bounded version of the reachability problem (Barnes et al. calls it
short
path problem
) as subroutine.
SPATH
(
u
,v,ʲ)
=
true
⃐
there is a path of length
ʲ
from
u
to
v
in
G
.
We can use an algorithm for SPATH as subroutine to solve Construct as follows.
Given
(
G
,
S
, ʲ)
, to check whether
v
∃
V
is at distance
ʲ
from some vertex in
S
,
first check whether SPATH
(
u
,v,ʲ)
is true for some
u
∃
S
and check for all
u
∃
S
,
SPATH
is false.
For a given algorithm for SPATH, let
T
(
u
,v,ʲ
−
1
)
(
n
, ʲ)
be its time complexity and
S
(
n
, ʲ)
n
3
be its space complexity. Then the time complexity of Construct is
O
(
)
T
(
n
, ʲ)
n
and its space complexity is
O
(
ʲ
)
+
S
(
n
, ʲ)
. Moreover, once
C
j
∅
is constructed,
n
reachability can be solved by making
ʲ
calls to SPATH
(
u
,
t
, ʲ)
(for all
u
∃
C
j
∅
).
n
4
Thus the total running time for the reachability algorithm will be
O
(
)
T
(
n
, ʲ)
and
n
the space bound will be
O
.
We will now focus on SPATH. We will use a divide and conquer approach as in
Savitch's algorithm to design an algorithm for SPATH. The problem with a direct
application of Savitch's algorithm is its running time: at each level of recursion
it cycles through all
n
nodes as a candidate for the middle node. This results in
O
(
ʲ
)
+
S
(
n
, ʲ)
n
log
n
(
)
time. Since we are interested in keeping the time polynomial, we can
