Information Technology Reference
In-Depth Information
label
s
∗
,andrecurse on the only child of the root. Following standard practice, we now
distinguish the different types of tree nodes.
Serial case:
Let the skeleton of the S-node
μ
be the simple cycle
s, v
1
,...,v
m−
1
,t,s
,
where (
s, t
) is the reference edge representing the parent of
μ
. The remaining edges
(
s, v
1
)
,...,
(
v
m−
1
,t
) correspond to the children
μ
1
,...,μ
m
of
μ
.Werecurse on
μ
1
,
label
v
1
,recurse on
μ
2
, and so on, until
μ
m
. Notice that we do not label
t
. Clearly, the
result is an
st
-ordering when assigning
t
the current valueofthecounter. The successor
lists of
s, v
1
,...,v
m−
1
are all sorted decreasingly duetoourinvariant,thus, are bitonic.
Parallel case:
We first check if one of the children
μ
1
,...,μ
m
of the P-node
μ
is a Q-
node. In that case we change the order of the children such that
μ
1
is the Q-node. Notice
that this implies a change in the embedding of
G
.Thenwerecurse on the children in
their reverse order, i.e.
μ
m
,...,μ
1
. Consider now the successor list
S
(
s
) of
s
:The
neighbors
w
1
,...,w
k
with 1
≤
i
≤
m
that are located in the induced subgraph of
μ
i
form a consecutive sequence in
S
(
s
):
...,w
1
,...,w
k
,w
i
+
1
,...,w
i
+1
S
(
s
)=
{
,...
}
k
neighbors in
μ
i
neighbors in
μ
i
+1
By our invariant, it follows that
ˀ
(
w
j
)
>ˀ
(
w
j
+1
) and since we recursed on
μ
1
,...,μ
m
in reverse order,
ˀ
(
w
k
)
>ˀ
(
w
i
+
1
) holds. Hence, the sequence is decreasing.
Rigid case:
We start by constructing a temporary ordering
ˀ
for the triconnected
skeleton
G
μ
=(
V
μ
,E
μ
) of the R-node
μ
using Lemma 1 and choosing the reference
edge (
s, t
) as input. Then we traverse the vertices of
V
μ
in the ordering as given by
ˀ
.
At a vertex
v
E
μ
with
ˀ
(
u
)
<ˀ
(
v
),
i.e., the incoming edges of
v
with respect to
ˀ
. Afterwards, we label
v
unless
v
=
t
.
The resulting ordering is not necessarily a bitonic
st
-ordering. We proceed in two steps:
First we derive some useful properties of
ˀ
and narrow down the problem. Then we ar-
gue that mirroring the embedding of some children of
μ
changes the successor lists such
that they become bitonic with respect to
ˀ
.
Let us take a closer look at the properties of
ˀ
: Since we labeled all
v ∈ V
μ
in
the order as provided by
ˀ
, for any two vertices
u,v ∈ V
μ
with
u
=
v
, it holds that
ˀ
(
u
)
<ˀ
(
v
) if and only if
ˀ
(
u
)
<ˀ
(
v
). Hence,
ˀ
is a feasible bitonic
st
-ordering
for
G
μ
. Recall that we recursed on the children in a special way. Consider a vertex
v
in the induced subgraph of a child
μ
uv
represented by the virtual edge (
u,v
)
∈
V
μ
,werecurse on the incident edges (
u,v
)
∈
∈
E
μ
with
ˀ
(
u
)
<ˀ
(
v
).Furthermore, assume that
v
is not a pole of
μ
uv
, i.e.,
u
=
v
=
v
.
Then
v
V
μ
with
ˀ
(
w
)
<ˀ
(
v
),thus
ˀ
(
w
)
<ˀ
(
v
)
<ˀ
(
v
). When now considering afourth vertex, say
w
, that is defined
similar as
v
, i.e., a non-pole vertex located in the subgraph induced by a virtual edge
(
x, w
)
has been labeled before
v
and after any
w
∈
⃒
ˀ
(
w
)
<ˀ
(
v
). Stemming from the special traversal of the edges, this property is of
particular interest when considering the successor lists.
Let
S
(
v
)=
∈
E
μ
with
ˀ
(
x
)
<ˀ
(
w
), then we may deduce the implication
ˀ
(
w
)
<ˀ
(
v
)
w
1
,...,w
h
,...,w
m
}ↂ
{
V
μ
be the successor list of
v
∈
V
μ
.See
Figure 3a for an example. Notice that
ˀ
(
w
1
)
<
>ˀ
(
w
m
) holds.
Furthermore, let
μ
1
,...,μ
m
be the corresponding children of
μ
that are represented
by the virtual edges (
v,w
1
)
,...,
(
v,w
m
) with
ˀ
(
v
)
<ˀ
(
w
i
) for 1
<ˀ
(
w
h
)
>
···
···
≤
i
≤
m
. Similar
