a suitable digraph kameda s method
s
{\displaystyle s}
,
t
{\displaystyle t}
added.
the same graph above after kameda s algorithm has run, showing dfs labels each vertex
an faster method pre-processing, due t. kameda in 1975, can used if graph planar, acyclic, , exhibits following additional properties: 0-indegree , 0-outdegree vertices appear on same face (often assumed outer face), , possible partition boundary of face 2 parts such 0-indegree vertices appear on 1 part, , 0-outdegree vertices appear on other (i.e. 2 types of vertices not alternate).
if
g
{\displaystyle g}
exhibits these properties, can preprocess graph in
o
(
n
)
{\displaystyle o(n)}
time, , store
o
(
log
n
)
{\displaystyle o(\log {n})}
bits per vertex, answering reachability queries pair of vertices in
o
(
1
)
{\displaystyle o(1)}
time simple comparison.
preprocessing performs following steps. add new vertex
s
{\displaystyle s}
has edge each 0-indegree vertex, , new vertex
t
{\displaystyle t}
edges each 0-outdegree vertex. note properties of
g
{\displaystyle g}
allow while maintaining planarity, is, there still no edge crossings after these additions. each vertex store list of adjacencies (out-edges) in order of planarity of graph (for example, clockwise respect graph s embedding). initialize counter
i
=
n
+
1
{\displaystyle i=n+1}
, begin depth-first traversal
s
{\displaystyle s}
. during traversal, adjacency list of each vertex visited left-to-right needed. vertices popped traversal s stack, labelled value
i
{\displaystyle i}
, ,
i
{\displaystyle i}
decremented. note
t
{\displaystyle t}
labelled value
n
+
1
{\displaystyle n+1}
,
s
{\displaystyle s}
labelled
0
{\displaystyle 0}
. depth-first traversal repeated, time adjacency list of each vertex visited right-to-left.
when completed,
s
{\displaystyle s}
,
t
{\displaystyle t}
, , incident edges, removed. each remaining vertex stores 2-dimensional label values
1
{\displaystyle 1}
n
{\displaystyle n}
. given 2 vertices
u
{\displaystyle u}
,
v
{\displaystyle v}
, , labels
l
(
u
)
=
(
a
1
,
a
2
)
{\displaystyle l(u)=(a_{1},a_{2})}
,
l
(
v
)
=
(
b
1
,
b
2
)
{\displaystyle l(v)=(b_{1},b_{2})}
,
l
(
u
)
<
l
(
v
)
{\displaystyle l(u)<l(v)}
if , if
a
1
≤
b
1
{\displaystyle a_{1}\leq b_{1}}
,
a
2
≤
b
2
{\displaystyle a_{2}\leq b_{2}}
, , there exists @ least 1 component
a
1
{\displaystyle a_{1}}
or
a
2
{\displaystyle a_{2}}
strictly less
b
1
{\displaystyle b_{1}}
or
b
2
{\displaystyle b_{2}}
, respectively.
the main result of method states
v
{\displaystyle v}
reachable
u
{\displaystyle u}
if and
only if
l
(
u
)
<
l
(
v
)
{\displaystyle l(u)<l(v)}
, calculated in
o
(
1
)
{\displaystyle o(1)}
time.
Comments
Post a Comment