Partitioning graphs of supply and demand
Partitioning graphs of supply and demand
复制标题
DOI：
10.1016/j.dam.2008.08.012
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;Xiao Zhou;Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Xiao Zhou;Takao Nishizeki
假设图G的每个顶点要么是供应顶点，要么是需求顶点，并被分配了一个正整数，称为供应或需求。每个需求顶点可以通过G中的边从至多一个供应顶点获得“能量”。因此，人们希望通过从G中删除边来将G划分为连通分量，使得每个分量C恰好具有一个供应顶点，其供应不小于C中所有需求顶点的需求总和。如果G没有这样的划分，则希望将G划分为连通分量，使得每个分量C或者没有供应顶点，或者恰好具有一个供应顶点，其供应不小于C中的需求总和，并且希望最大化具有供应顶点的所有组件中的需求总和。我们处理这样一个极大化问题，它即使对于树也是NP-难的，对于一般图也是强NP-难的。在这篇文章中，我们证明了对于串并图和部分k-树，即具有有界树宽的图，该问题可以在伪多项式时间内求解。
Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a 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 has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G does not have such a partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series–parallel graphs and partial k-trees–that is, graphs with bounded tree-width.