The shifting algorithm technique for the partitioning of trees

DOI10.1016/0166-218X(94)00143-2zbMath0833.68088MaRDI QIDQ1900135

Yehoshua Perl, Ronald I. Becker

Publication date: 1995

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

zbMATH Keywords

shifting algorithm techniquetop-down greedy technique

Mathematics Subject Classification ID

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

Related Items (15)

On the uniform edge-partition of a tree ⋮ Subset sum problems with digraph constraints ⋮ Improved algorithms for path partition and related problems ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ Cardinality constrained connected balanced partitions of trees under different criteria ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Algorithms for uniform centered partitions of trees ⋮ Uniform and most uniform partitions of trees ⋮ Partitioning of trees for minimizing height and cardinality ⋮ On the complexity of isoperimetric problems on trees ⋮ Unnamed Item ⋮ Path equipartition in the Chebyshev norm ⋮ A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree

Uses Software

• PERL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A shifting algorithm for constrained min-max partition on trees
• Efficient implementation of a shifting algorithm
• Parallel concepts in graph theory
• Most uniform path partitioning and its use in image processing
• Efficient Optimization of Monotonic Functions on Trees
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• Shifting algorithms for tree partitioning with general weighting functions
• Circuit partitioning with size and connection constraints
• Max-Min Tree Partitioning

This page was built for publication: The shifting algorithm technique for the partitioning of trees