講演抄録/キーワード |
講演名 |
2008-05-13 11:15
マンハッタンモデルにおける無線ネットワーク上の最小エネルギーブロードキャストについて ○山田敏規(埼玉大) COMP2008-9 |
抄録 |
(和) |
小文は最小のエネルギーで無線ネットワーク上でブロードキャストを行うことを目的とした
MECBS問題の特別な場合を考える.
この特別な場合はニューヨークのマンハッタンのような沢山のビルを持つ
都心の状況をモデル化している.
最初に,この問題がNP-困難であることが示される.
次に,最小全域木に基づいたアルゴリズムMSTがこの問題に対する
$4$-近似アルゴリズムであることを示す. |
(英) |
This paper considers a special case of MECBS(Minimum Energy Consumption
Broadcast Subgraph) problem, which is motivated by
braodcasting on wireless networks with minimum energy.
This special case models a situation of a downtown with a lot of buildings
such as Manhattan in NY.
First, this problem is proved to be NP-hard, and then MST, an algorithm
based on minimum spanning tree, is shown to be
a $4$-approximation algorithm for this problem. |
キーワード |
(和) |
無線ネットワーク / ブロードキャスト / MECBS問題 / NP-困難 / MST / 近似アルゴリズム / / |
(英) |
Wireless Networks / Broadcasting / MECBS problem / NP-hard / MST / Approximation Algorithms / / |
文献情報 |
信学技報, vol. 108, no. 29, COMP2008-9, pp. 9-16, 2008年5月. |
資料番号 |
COMP2008-9 |
発行日 |
2008-05-06 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2008-9 |