Parametric Power Supply Networks

概要

論文の詳細を見る
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a supply or a demand. All demands and supplies are nonnegative constant numbers in a steady network, while they are functions of a variable λ in a parametric network. Each demand vertex can receive "power" from exactly one supply vertex through edges in G. One thus wishes to partition G to connected components by deleting edges from G so that each component has exactly one supply vertex whose supply is at least the sum of demands in the component. The "partition problem" asks whether G has such a partition. If G has no such partition, one wishes to find a maximum number r*, 0 ≦ r < 1, such that G has such a partition when every demand is reduced to r* times the original demand. The "maximum supply rate problem" asks to find such a number r*. In this paper, we deal with a network in which G is a tree, and first give a polynomial-time algorithm for the maximum supply rate problem for a steady tree network, and then give an algorithm for the partition problem on a parametric tree network, which takes pseudo-polynomial time if all the supplies and demands are piecewise linear functions of λ.
2013-02-22