The shifting algorithm technique for the partitioning of trees

Ronald I. Becker, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


In this paper we survey a design technique for partitioning on trees. This technique, the shifting algorithm technique, is a top-down greedy technique. A partition of a tree is represented by associating cuts with edges of the tree. The basic operation of the technique is a local transformation called a shift of a cut from an edge to an adjacent edge of the tree. We review several shifting algorithms for different optimization criteria for partitioning. In these algorithms, different shifts and different greedy decisions are utilized. A mathematical framework created for validity proofs of shifting algorithms is introduced. Various applications are outlined.

Original languageEnglish (US)
Pages (from-to)15-34
Number of pages20
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Sep 8 1995

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'The shifting algorithm technique for the partitioning of trees'. Together they form a unique fingerprint.

Cite this