Efficient implementation of a shifting algorithm

DOI10.1016/0166-218X(85)90041-1zbMath0585.68067OpenAlexW4213040960MaRDI QIDQ1070825

Yehoshua Perl, Uzi Vishkin

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(85)90041-1

zbMATH Keywords

time complexitytree partitioningmin-max partitioningundirected node-weighted tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The shifting algorithm technique for the partitioning of trees ⋮ Partitioning a matrix to minimize the maximum cost ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ A linear-time algorithm for finding an edge-partition with max-min ratio at most two ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Algorithms for uniform centered partitions of trees ⋮ A shifting algorithm for constrained min-max partition on trees ⋮ Uniform and most uniform partitions of trees ⋮ Minmax subtree cover problem on cacti ⋮ Most uniform path partitioning and its use in image processing ⋮ On a 2-dimensional equipartition problem ⋮ Continuous bottleneck tree partitioning problems ⋮ A shifting algorithm for continuous tree partitioning

Cites Work

• A shifting algorithm for constrained min-max partition on trees
• Shifting algorithms for tree partitioning with general weighting functions
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• A Linear Tree Partitioning Algorithm

This page was built for publication: Efficient implementation of a shifting algorithm