| 講演名 | 2007-09-28 P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般) 三輪 直樹, 趙 亮, 永持 仁, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | リアルタイムの配信を目的とするP2Pシステムにおいて,各中継ノードの能力を超えないで遅延を最小にする必要がある.本論文は,この問題を有向グラフにおける出次数制約つき深さ最小木問題として定式化する.この問題は一般的にNP困難であるので,近似アルゴリズムとして集中型アルゴリズムと分散型アルゴリズムを提案する.これらのアルゴリズムを用いて実験した結果,CPLEXを用いた厳密解法に比べ,短時間で質の高い解が得られることが確認できた. |
| 抄録(英) | It is necessary to minimize delay from a sender with considering the ability of each broadcast node when we design P2P system for real time streaming. In this paper, to solve this problem, we aim at constructing the minimum depth tree satisfying outdegree constraint in a directed graph. This problem is generally NP-hard, so we propose an centering model algprithm and an distributing model algorithm. As a result of having experimented by using these algorithms, we have confirmed that these algorithms give a high quality solution compared with exact algorithm by using CPLEX. |
| キーワード(和) | P2Pシステム / 深さ最小木 |
| キーワード(英) | P2P system / minimum depth tree |
| 資料番号 | CQ2007-54,OIS2007-44,IE2007-51 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IE |
|---|---|
| 開催期間 | 2007/9/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Image Engineering (IE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般) |
| サブタイトル（和） | |
| タイトル（英） | On the construction of the minimum depth tree for P2P system |
| サブタイトル（和） | |
| キーワード(1)（和/英） | P2Pシステム / P2P system |
| キーワード(2)（和/英） | 深さ最小木 / minimum depth tree |
| 第 1 著者 氏名（和/英） | 三輪 直樹 / Naoki MIWA |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 趙 亮 / Liang ZHAO |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 永持 仁 / Hiroshi NAGAMOCHI |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2007-09-28 |
| 資料番号 | CQ2007-54,OIS2007-44,IE2007-51 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 231 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |