MSPP)" is to find a feasible partition π of G such that d(π) 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." />
 For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply GraphsSatoshi TAOKA  Kazuya WATANABE  Toshimasa WATANABE  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.4   pp.1049-1057Publication Date: 2006/04/01 Online ISSN: 1745-1337Print ISSN: 0916-8508Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)Category: Keyword: graphs,  partitioning problems,  heuristic algorithms,  optimal algorithms,  demand,  supply,  Full Text: PDF(436.4KB)>>Buy this Article Summary:  Let G = (D ∪ S,E) be an undirected graph with a vertex set D ∪ 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 ≠ and S ≠ 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' ⊆ D ∪ S, the demand of V' is defined by d(V') = Σv∈V'∩Dd(v) if V' ∩ D ≠ or d(V') = 0 if V' ∩ D = . Let s(S) = Σv∈S s(v). Any partition π = {V1,..., Vr} (|S| r |D ∪ S|) of D ∪ S is called a feasible partition of G if and only if π satisfies the following (1) and (2) for any k = 1,..., r: (1) |Vk ∩ S|1, and (2) if Vk ∩ S = {uk} then the induced subgraph G[Vk] of G is connected and d(Vk)s(uk). The demand d(π) of π is defined by d(π)=d(Vk). The "Maximum-Supply Partitioning Problem (MSPP)" is to find a feasible partition π of G such that d(π) 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.