Approximability of partitioning graphs with supply and demand

DOI10.1016/j.jda.2008.03.002zbMath1154.05328OpenAlexW2172083980MaRDI QIDQ1002107

Takao Nishizeki, Takehiro Ito, Xiao Zhou, Erik D. Demaine

Publication date: 23 February 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.03.002

zbMATH Keywords

approximation algorithmseries-parallel graphdemandFPTASsupplygraph partition problemMAXSNP-hard

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Consumer behavior, demand theory (91B42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

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 ⋮ Minimum cost partitions of trees with supply and demand ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Partitioning of supply/demand graphs with capacity limitations: an ant colony approach ⋮ On the complexity of reconfiguration problems ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs ⋮ A strongly polynomial time algorithm for the maximum supply rate problem on trees ⋮ 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
• Optimization, approximation, and complexity classes
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximability of Partitioning Graphs with Supply and Demand
• PARTITIONING TREES OF SUPPLY AND DEMAND

This page was built for publication: Approximability of partitioning graphs with supply and demand