講演抄録/キーワード |
講演名 |
2015-05-22 10:00
階層制約のある情報フロー問題に関する計算理論的考察 ○武田友希・楫 勇一・伊藤 実(奈良先端大) IT2015-11 EMM2015-11 |
抄録 |
(和) |
情報フロー問題は,情報の持つ特性を考慮した上で,ネットワーク上で情報を流通させる方式を検討する問題である.ある種の情報フロー問題では,線形ネットワーク符号が重要な役割を果たすことが知られているが,一般的な問題における線形ネットワーク符号の特性については明らかでない部分も多い.本研究では,与えられた情報フロー問題が線形解を持つか否か判定する問題において,Lehman らによる既存研究を拡張し,メッセージ集合に階層制約のある情報フロー問題について計算理論的な考察を行う.階層制約は,現実のネットワークサービスの中でも頻繁に発生する事例であり,この制約下の情報フロー問題を考えることは理論的に興味深いだけでなく,
実用的観点からも重要である.他の制約と組み合わせて新しく導入される9種類の情報フロー問題それぞれが,Lehman の3カテゴリのいずれに分類されるかを明らかにする. |
(英) |
An information flow problem discusses how to distribute information over a complicated network. It is known that the technique of the network coding plays an essential role in a certain type of information flow problems,
but not so much are known about other types of the problem. As an extension of Lehman's investigation, this study introduces a hierarchy constraint of messages, and discusses the computational complexity of the problem to determine if a given information flow problem has a linear solution or not. Nine classes of problems are newly defined, and classified to one of three categories that were discovered by Lehman. |
キーワード |
(和) |
情報フロー問題 / ネットワーク符号 / 計算理論 / 階層制約 / メッシュネットワーク / / / |
(英) |
information flow problem / network coding / computational complexity / hierarchy constraint / mesh network / / / |
文献情報 |
信学技報, vol. 115, no. 37, IT2015-11, pp. 57-62, 2015年5月. |
資料番号 |
IT2015-11 |
発行日 |
2015-05-14 (IT, EMM) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2015-11 EMM2015-11 |
|