Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs(<Special Section>Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)

概要

論文の詳細を見る
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≠0 and S≠0 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≠0 or d(V')=0 if V'∩D=0. 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∩S|≤1, 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(π)=Σ_<V_k∩S>≠0>d(V_k). 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.
社団法人電子情報通信学会の論文
2006-04-01