| Presentation | 2005-01-28 Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs Kazuya WATANABE, Satoshi TAOKA, Toshimasa WATANABE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Let G=(V_d∪V_s, E) be an undirected graph with a vertex set V_d∪V_s and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set V_d and a supply vertex set V_s. We assume that V_d≐̸0 and V_s≐̸0 in this paper. Each demand or supply vertex ν has a positive real number d(ν) or s(ν), called the demand or supply of ν, respectively. For any subset V′⊆V_d∪V_s, the demand of V′ is defined by d(V′)=Σ_<ν⋴V′∩V_d>d(ν) if V′∩V_s≐̸0 or d(V′)=0 if V′∩V_s=0. Any partition π={V_1, …, V_p} (p≧1) of V_d∪V_s such that |V_k∩V_s|≦1, the induced subgraph G[V_k] of G is connected, and if |V_k∩V_s|≦{u_k} then d(V_k)≦s(u_k), for any k-1≦k≦p is called a feasible partition of G. The demand d(π) of π is defined by d(π)=Σ_<1≦k≦p>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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graphs / partitioning problems / heuristic algorithms / optimal algorithms / demand / supply |
| Paper # | COMP2004-67 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/1/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs |
| Sub Title (in English) | |
| Keyword(1) | graphs |
| Keyword(2) | partitioning problems |
| Keyword(3) | heuristic algorithms |
| Keyword(4) | optimal algorithms |
| Keyword(5) | demand |
| Keyword(6) | supply |
| 1st Author's Name | Kazuya WATANABE |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Satoshi TAOKA |
| 2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 3rd Author's Name | Toshimasa WATANABE |
| 3rd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| Date | 2005-01-28 |
| Paper # | COMP2004-67 |
| Volume (vol) | vol.104 |
| Number (no) | 642 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |