Efficient implementation of a shifting algorithm

Yehoshua Perl, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

An efficient implementation of the shifting algorithm [2] for min-max tree partitioning is given. The complexity is reduced from ORk3 + kn) to O(Rk(k + log d) + 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 the new junction tree data structure which suggests a succinct representation for subsets of edges, of a given tree, that preserves the interrelation betqween the edges on the tree.

Original languageEnglish (US)
Pages (from-to)71-80
Number of pages10
JournalDiscrete Applied Mathematics
Volume12
Issue number1
DOIs
StatePublished - Sep 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Efficient implementation of a shifting algorithm'. Together they form a unique fingerprint.

Cite this