Approximability of partitioning graphs with supply and demand
type: Item
instance of: scholarly article
title: Approximability of partitioning graphs with supply and demand
zbMATH Open document ID: 1154.05328
author: Takehiro Ito
author: Erik D. Demaine
author: Xiao Zhou
author: Takao Nishizeki
published in: Journal of Discrete Algorithms
publication date: 2009-02-23T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 91B42
zbMATH DE Number: 5509893
zbMATH Keywords: approximation algorithm
zbMATH Keywords: demand
zbMATH Keywords: FPTAS
zbMATH Keywords: graph partition problem
zbMATH Keywords: MAXSNP-hard
zbMATH Keywords: series-parallel graph
zbMATH Keywords: supply
MaRDI profile type: Publication
full work available at URL: j.jda.2008.03.002
OpenAlex ID: W2172083980
cites work: Easy problems for tree-decomposable graphs
cites work: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
cites work: Q4198056
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximability of Partitioning Graphs with Supply and Demand
cites work: PARTITIONING TREES OF SUPPLY AND DEMAND
cites work: Q4298260
cites work: Optimization, approximation, and complexity classes
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
DOI: 10.1016/J.JDA.2008.03.002
description: scientific article; zbMATH DE number 5509893