Mikhail Atallah.

Finding Euler tours in parallel online

. (page 1 of 1)
Online LibraryMikhail AtallahFinding Euler tours in parallel → online text (page 1 of 1)
Font size
QR-code for this ebook


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^),


1

Online LibraryMikhail AtallahFinding Euler tours in parallel → online text (page 1 of 1)