Shifting algorithms for tree partitioning with general weighting functions

Ronald I. Becker, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

Recently two shifting algorithms were designed for two optimum tree partitioning problems: The problem of max-min q-partition [4] and the problem of min-max q-partition [1]. In this work we investigate the applicability of these two algorithms to max-min and min-max partitioning of a tree for various different weighting functions. We define the families of basic and invariant weighting functions. It is shown that the first shifting algorithm yields a max-min q-partition for every basic weighting function. The second shifting algorithm yields a min-max q-partition for every invariant weighting function. In addition a modification of the second algorithm yields a min-max q-partition for the noninvariant diameter weighting function.

Original languageEnglish (US)
Pages (from-to)101-120
Number of pages20
JournalJournal of Algorithms
Volume4
Issue number2
DOIs
StatePublished - Jun 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Shifting algorithms for tree partitioning with general weighting functions'. Together they form a unique fingerprint.

Cite this