Information Technology Reference
In-Depth Information
not afford to cycle through all
n
nodes. Instead, we will divide the set of nodes into
μ
equivalence classes and use a Savitch-like divi
de a
nd conquer on these equivalence
class
es (in
stead of the vertices). For
μ
=
2
O
(
≥
log
n
)
the depth of recursion will be
(
≥
log
n
O
and this approach will result in polynomial time.
For a parameter
)
μ
, partition the vertex set into
μ
equivalence classes
[
1
]
,
[
2
]
,...
[
μ
]
where vertex
x
∃[
a
]⃐
x
⃒
a
(
mod
μ)
. Each equivalence class has
n
μ
elements (except for the last one whose cardinality may be smaller). We will
use
etc to denote these equivalence classes of vertices. Although this is
not a very standard notation, the
i
th
vertex of the equivalence class
[
a
]
,
[
b
]
,
[
c
]
[
a
]
(according to
some fixed ordering) will be denoted by
.
Consider the procedure Modified-Savitch
(
[
a
]
(
i
)
G
,
[
a
]
,
[
b
]
,
X
,
l
)
where
[
a
]
and
[
b
]
n
are equivalence classes of vertices,
X
is an
binary array, and
l
is a length para-
meter. This procedure returns a binary vector
Y
of size
μ
n
μ
, where
Y
[
j
]=
1
⃐
i
so that
X
[
i
]=
1and there is a path
2
l
from
of length
[
a
]
(
i
)
to
[
b
]
(
j
)
SPATH
(
u
,v,ʲ)
can be solved by one call to Modified-Savitch with parameter
(
[
a
]
,
[
b
]
,
X
u
,
log
2
ʲ
)
where
[
a
]=
the equivalence class containing
u
,
[
b
]=
the
equivalence class containing
, and
X
u
is the vector with 1 in the index corresponding
to
u
and 0 otherwise. There is a path from
u
to
v
v
if and only if there is a 1 in the
index corresponding to
in the output vector
Y
. Below is a recursive version of the
algorithm Modified-Savitch.
v
Modified-Savitch
(
G
,
[
a
]
,
[
b
]
,
X
,
l
)
If
l
=
0 then
If
[
a
]=[
b
]
then
Y
∞
X
Else
Y
[
j
]=
1iff
i
such that there is an edge from
[
a
]
(
i
)
to
[
b
]
(
j
)
Else
Y
∞
0
For
c
=
1to
μ
Z
∞
Modified-Savitch
(
G
,
[
a
]
,
[
c
]
,
X
,
l
−
1
)
Y
c
∞
Modified-Savitch
(
G
,
[
c
]
,
[
b
]
,
Z
,
l
−
1
)
Y
∞
Y
ₒ
Y
c
Return
Y
Correctness of Modified-Savitch is easy to prove. Its time and space bounds
can be estimated using the following recurrences:
n
μ
)
+
S
(
l
)
=
O
(
S
(
l
−
1
)
n
μ
)
×
=
O
(
l
T
(
l
)
=
μ
×
2
×
T
(
l
−
1
)
+
O
(
n
)
l
+
1
=
(
2
μ)
×
O
(
n
)
