Partitioning a weighted tree into subtrees with weights in a given range

DOI10.1007/s00453-010-9485-yzbMath1239.05150OpenAlexW2156680550MaRDI QIDQ2428691

Takao Nishizeki, Xiao Zhou, Takehiro Ito, Michael Schröder, Takeaki Uno

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9485-y

zbMATH Keywords

treealgorithmdynamic programmingfast Fourier transformpolynomial-timegraph partitionsubtree

Mathematics Subject Classification ID

Trees (05C05) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (4)

An overview of graph covering and partitioning ⋮ Metaheuristics for the minimum gap graph partitioning problem ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ Uniform and most uniform partitions of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Most uniform path partitioning and its use in image processing
• A shifting algorithm for continuous tree partitioning
• A tabu search heuristic and adaptive memory procedure for political districting
• Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• A Linear Tree Partitioning Algorithm
• Fair dissections of spiders, worms, and caterpillars

This page was built for publication: Partitioning a weighted tree into subtrees with weights in a given range