Approximability of partitioning graphs with supply and demand
Approximability of partitioning graphs with supply and demand
复制标题
DOI：
10.1016/j.jda.2008.03.002
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;E. Demaine;Xiaoping Zhou;Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;E. Demaine;Xiaoping Zhou;Takao Nishizeki
假设图G的每个顶点或者是供给顶点或者是需求顶点，并被赋予一个正的真实的数，称为供给或需求。每个需求顶点可以通过G中的边从至多一个供应顶点接收“功率”。因此，人们希望通过从G中删除边来将G划分为连通分量，使得每个分量C要么没有供应顶点，要么恰好有一个供应顶点，其供应至少是C中的需求之和，并且希望最大化满足，即，所有具有供应顶点的分量中的需求之和。这个最大化问题是已知的NP-困难，甚至树有一个供应顶点和强NP-困难的一般图。在本文中，我们专注于问题的可逼近性。我们首先证明了这个问题是MAXSNP-困难的，因此除非P=NP，否则一般图没有多项式时间近似方案（PTAS）。然后，我们提出了一个完全多项式时间近似计划（FPTAS）的串-并行图恰好有一个供应顶点。
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P=NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex.