Online Library → Yehoshua Perl → Efficient implementation of a shifting algorithm → online text (page 1 of 1)

Font size

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

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 Library → Yehoshua Perl → Efficient implementation of a shifting algorithm → online text (page 1 of 1)