Browse Prior Art Database

Efficient Implementation of A Shifting Algorithm

IP.com Disclosure Number: IPCOM000128218D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Yehoshua Perl: AUTHOR [+4]

Abstract

A technique of shifting algorithms for tree partitioning problems was recently developed in a sequence of papers ( [PS] , [BPS], [BPI, [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] ).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

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

t. Introduction

A technique of shifting algorithms for tree partitioning problems was recently developed in a sequence of papers ( [PS] , [BPS], [BPI, [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

(Equation Omitted)

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 data 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 intermediate level description to form a low-level implementation of the algorithm.

2: Nigh-Level Description

Let T(V,E) be a tree where V is the set of vertices and E is the set of (undirected) edges. We associate a nonnegative weight w(v) with every vertex veV. A g-partition of the tree T into q connected components

(Equation Omitted)

is obtained by deleting

New York University Page 1 Dec 31, 1983

Page 2 of 11

Efficient Implementation of A Shifting Algorithm

(Equation Omitted)

(Equation Omitted)

edges of T where

(The definition allows empty

(Equation Omitted)

The weigh t W(TI) of each component T, is the sum of the weights of its vertices. Each Ti is a tree, hence we may refer to it as a subtree of T.

The min-max g-partition problem. Find a q-partition of T minimizing Tiftcl W(Ti)

Definitions and Notations ,,

For two vertices

(Equation Omitted)

define

(Equation Omitted)

the distance between a and v in T, to be the number of edges in the loop-free path from a to v in
T. The radius

(Equation Omitted)

A vertex that yields the minimum in the definition of R is called a

(Equation Omitted)

center of T. Add an auxiliary vertex r to T

(Equation Omitted)

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. (f...