Copyright
Yehoshua Perl.

Efficient implementation of a shifting algorithm online

. (page 1 of 1)
Online LibraryYehoshua PerlEfficient implementation of a shifting algorithm → online text (page 1 of 1)
Font size
QR-code for this ebook


M:^-'



Computer Science Department



TECHNICAL REPORT



Efficient Implementation of
A Shifting Algorithm

by

Yehoshua Perl*

and

Uzi Vishkin



Technical Report No. 57
February 1983



NEW YORK UNIVERSITY



Department of Computer Science
Courant Institute of Mathematical Sciences

251 MERCER STREET, NEW YORK, N.Y. 10012



Efficient Implementation of
A Shifting Algorithm

by

Yehoshua Perl*

and

Uzi Vishkin



Technical Report No. 57
February 1983



This work was supported in part by the National Science Foundation
and the Applied Mathematical Sciences Program of the Department
of Energy, Grant Numbers NSF-MCS79-07804 and DE-AC02-76ER03077
respectively.

*Rutgers University, New Brunswick, N.J. 08903



CP



EFFICIENT IMPLEMENTATION OF A SHIFTING ALGORITHM

Yehoshua Perl

Rutgers University

New Brunswick, NJ 08903

AND

Uzi Vishkin

Courant Institute

New York University

251 Mercer Street

New York, NY 10012



1. Introduction

A technique of shifting algorithms for tree partitioning problems was recently developed
in a sequence of papers ([PS], [BPS], [BP], [ABP]) This technique is a top-down greedy
technique rather than the bottom up approach used usually for such problems (see e.g.,
[KM] , [KH] ).



An efficient implementation of the shifting algorithm ([BPS]) for min-max tree partitioning
is given. The complexity is reduced from 0(Rk + kn) to 0(Rk(k + logd) + n) where a tree
of n vertices, radius of R edges, and maximum degree d is partitioned into k+ 1 subtrees.



The improvement is mainly due to a datj structure which suggests a succinct
representation for subsets of edges, of a given tree, that preserves the interrelation
between the edges on the tree. Section 2 introduces both the min-max tree partitioning
problem and high-level description of the shifting algorithm which was given in [BPS].
Section 3 presents an implementation scheme of the algorithm which forms an
intermediate- level description of the algorithm. Section 4 introduces two data-structures.
It is then shown how to utilize them by the intermediju level description to form a low-
level implementation of the algorithm.

2. High-Level Description

Let T(V.E) be a tree whare V is the set of vertices and E is the set of (undirected)
edges. We associate a nonnegative weight w(v) withi gvery vertex veV. A q-partition of

the tree T into q connected components T^,T T is obtained by deleting i, i

center of T Add an auxiliary vertex r to T with w(r) = 0. Connect r to a center by an
auxiliary edge. Transform the new tree into a rooted tree by choosing r to be the root and
imposing a top-down direction on the edges. From now on we denote by T the new
rooted tree.

In this paper we use the usual terminology of graph theory. If e is a directed edge
incident from v^ and incident to v denoted by v — ^ v then we refer to v as tail(e)
and to V as head(e) . Edge e is said to be the father of edge e if head(e) = taiKe ), and



in this case, e. is said to be the son of edge e. Edges e. and e^ are said to be brothers
if taiKe,) = taiKe^.'-

Edge e



path from e to e_ (resp e. to e.). Tho definitions of father, son, descendent and

ancestor extend in the obvious way to vertices. Consider a function f:{1.2 k} — 'E. Each

such function represents the i, i


1

Online LibraryYehoshua PerlEfficient implementation of a shifting algorithm → online text (page 1 of 1)