Experimental evaluation of maximum-supply partitioning algorithms for demand-supply graphs
Let G = (D boolean OR S, E) be an undirected graph with a vertex set D boolean OR S and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set D and a supply vertex set S. We assume that D not equal empty set and S not equal empty set in this paper. Each demand or supply vertex v has a positive real number d(v) or s(v), called the demand or supply of v, respectively. For any subset V' subset of D boolean OR S, the demand of V' is defined by d(V') = Sigma(v is an element of V'boolean AND D) d(v) if V' boolean AND D not equal empty set or d(V') = 0 if V' boolean AND D = empty set. Let s(S) = Sigma(v is an element of S) s(v). Any partition pi = {V-1,..., V-r} (\S\ <= r <= \D boolean OR S\) of D boolean OR S is called a feasible partition of G if and only if pi satisfies the following (1) and (2) for any k = 1,...r: (1) 1 V-k boolean AND S\ <= 1, and (2) if V-k boolean AND S = {u(k)} then the induced subgraph G[V-k] of G is connected and d(V-k) <= s(u(k)). The demand d(pi) of pi is defined by d(pi) = Sigma V-k boolean AND S not equal empty set d(V-k). The "Maximum-Supply Partitioning Problem (MSPP)" is to find a feasible partition pi of G such that d(pi) is maximum among all feasible partitions of G. We implemented not only existing algorithms for obtainity heuristic or optimum solutions to MSPP but also those that are corrected or improved from existing ones. In this paper we show comparison of their capability based on computational experiments.
supply demand graphs partitioning problems heuristic algorithms optimal algorithms