Minimum cost partitions of trees with supply and demand

DOI10.1007/s00453-011-9573-7zbMath1255.68073OpenAlexW2090058386MaRDI QIDQ1934311

Xiao Zhou, Takuya Hara, Takehiro Ito, Takao Nishizeki

Publication date: 28 January 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9573-7

zbMATH Keywords

treeapproximation algorithmFPTASgraph partitiondemand vertexsupply vertexdirected edge

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Parameterized Minimum Cost Partition of a Tree with Supply and Demand, A heuristic approach for dividing graphs into bi-connected components with a size constraint, Partitioning of supply/demand graphs with capacity limitations: an ant colony approach, Partition on trees with supply and demand: kernelization and algorithms, Parametric Power Supply Networks, Parametric power supply networks, A heuristic method for solving the problem of partitioning graphs with supply and demand

Cites Work

• Unnamed Item
• Unnamed Item
• Partitioning graphs of supply and demand
• Approximability of partitioning graphs with supply and demand
• Minimum Cost Partitions of Trees with Supply and Demand
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• PARTITIONING TREES OF SUPPLY AND DEMAND
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem