Font size

Computer Science Department

TECHNICAL REPORT

FINDING EULER TOURS IN PARALLEL

By

Mikhail Atallah

and

Uzi Vishkin

Technical Report #134

Ultranote #73

(a)

o

n

I

Eh

03

u

D

O

-P

u

0)

U 3 .

W -C u M

O -H C M

\4-> ^a vj

:d K n) iliin' ,ind n

processors .

The goal of Step A. I Is to compute Into the vector SUCC a large circuit which

will alternate between edges of G and edges of T and have two properties: (1) The

edges of T will appear on It In an order of an F.uler circuit of T. (2) The edges

of G will appear on It In an order of an Euler circuit of G. We concentrate on

achieving the first property. Interestingly, the second property will follow

without further care.

Step 4.1. Recall the Idea of finding an Euler circuit of T using circular

succession assignments.

It Is trivial to obtain circular succession for each real-vertex v of V,: Let

deg(v) = d In T and let the d adjacent edges of v In T be { v,uq} , . . . , ( v ,u j_i } .

Set SUCC((u^,v)) := (v.u^+i ^^^ ^) , for < i < d-1.

It is more Interesting to obtain circular succession for each circuit-vertex w of

^1-

Let deg(w) = d in T and let the d adjacent edges of w in T be { Vq ,w} , . . . , { Vjj_^ ,w} .

Recall that Vq,.,.,vj_^ are real-vertices. Let (l^.v^) be CERTIFICATE( { v^ ,w} ) ,

for < a < d-1. All these d certificate edges appear on the circuit w (In G) in

some circular order. The key idea in this step is to use this circular order in

order to obtain a circular succession with respect to T. This is done as follows

(Say that following Step 1 SUCC( (1^ ,v^ ) ) = (v^,j^),

TECHNICAL REPORT

FINDING EULER TOURS IN PARALLEL

By

Mikhail Atallah

and

Uzi Vishkin

Technical Report #134

Ultranote #73

(a)

o

n

I

Eh

03

u

D

O

-P

u

0)

U 3 .

W -C u M

O -H C M

\4-> ^a vj

:d K n) iliin' ,ind n

processors .

The goal of Step A. I Is to compute Into the vector SUCC a large circuit which

will alternate between edges of G and edges of T and have two properties: (1) The

edges of T will appear on It In an order of an F.uler circuit of T. (2) The edges

of G will appear on It In an order of an Euler circuit of G. We concentrate on

achieving the first property. Interestingly, the second property will follow

without further care.

Step 4.1. Recall the Idea of finding an Euler circuit of T using circular

succession assignments.

It Is trivial to obtain circular succession for each real-vertex v of V,: Let

deg(v) = d In T and let the d adjacent edges of v In T be { v,uq} , . . . , ( v ,u j_i } .

Set SUCC((u^,v)) := (v.u^+i ^^^ ^) , for < i < d-1.

It is more Interesting to obtain circular succession for each circuit-vertex w of

^1-

Let deg(w) = d in T and let the d adjacent edges of w in T be { Vq ,w} , . . . , { Vjj_^ ,w} .

Recall that Vq,.,.,vj_^ are real-vertices. Let (l^.v^) be CERTIFICATE( { v^ ,w} ) ,

for < a < d-1. All these d certificate edges appear on the circuit w (In G) in

some circular order. The key idea in this step is to use this circular order in

order to obtain a circular succession with respect to T. This is done as follows

(Say that following Step 1 SUCC( (1^ ,v^ ) ) = (v^,j^),

1