
For FullText 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 MaximumSupply Partitioning Algorithms for DemandSupply Graphs
Satoshi TAOKA Kazuya WATANABE Toshimasa WATANABE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.4
pp.10491057 Publication Date: 2006/04/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e89a.4.1049
Print ISSN: 09168508 Type 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)>>
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'∩D}d(v) if V' ∩ D ≠ or d(V') = 0 if V' ∩ D = . Let s(S) = Σ_{v∈S} s(v). Any partition π = {V_{1},..., V_{r}} (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) V_{k} ∩ S1, and (2) if V_{k} ∩ S = {u_{k}} then the induced subgraph G[V_{k}] of G is connected and d(V_{k})s(u_{k}). The demand d(π) of π is defined by d(π)=d(V_{k}). The "MaximumSupply 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.

