講演抄録/キーワード |
講演名 |
2006-04-26 09:20
負荷分散セミマッチングにおける最適性について ○原田雄太・小野廣隆・定兼邦彦・山下雅史(九大) |
抄録 |
(和) |
本研究で扱う問題は2部グラフにおけるセミマッチング問題である.セミマッチングとは,2部グラフ$G=(U \cup V,E)$において各$U$の頂点が1つの$V$の頂点と対を成す枝の集合である.これまで,各$V$の頂点の次数が最も均等化されるようなセミマッチングを求める問題(負荷分散セミマッチング問題)の研究が行われている.それに対し,本研究では重み付き2部グラフにおける最小重み負荷分散セミマッチング問題を定式化し,アルゴリズムを提案する. |
(英) |
We consider the problem of finding a semi-matching for a bipartite graph $G = (U \cup V,E)$. A semi-matching is defined as a set of edges, $M \subseteq E$, such that cach vertex in $U$ is an endpoint of exactly one edge in $M$. In the past, the load-balancing semi-matching problem of obtaining a semi-matching such that the degrees of each $V$ vertex are balanced has been studied. While on the other hand, we newly formulate the min-weight load-balancing problem for weighted bipartite graphs and propose an algorithm. |
キーワード |
(和) |
2部グラフ / セミマッチング / スケジューリング問題 / 無線LAN / / / / |
(英) |
Bipartite Graph / Semi-Matching / Scheduling Problem / Wireless LAN / / / / |
文献情報 |
信学技報, vol. 106, no. 29, COMP2006-1, pp. 1-8, 2006年4月. |
資料番号 |
COMP2006-1 |
発行日 |
2006-04-19 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|