| 講演名 | 1996/12/6 木構造のファイル複製ネットワークの最適な2 : ファイルスケジューリングについて 田内 秀和, 金子 美博, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ファイルスケジユーリングとは,ネットワークNの外からある点(始点)にファイルJが与えられ,Nの内部で,Jのコピーが転送され,各点からNの外へその点の需要値分だけJのコピーが取り出されるようなJの転送方法である.最適なファイルスケジユーリングとは,コピー及び転送に必要な総コストが最小であるファイルスケジユーリングのことである.l種類のファイル転送の場合でも最適なファイルスケジユーリングを求めるのは一般的にはNP困難である本報告では,有向木の構造であり,点コスト及び枝コストに条件のあるNに対して,2種類のファイルJ_1及びJ_2を転送する場合(2-ファイルスケジユーリング)を考える.その結果,各点において,J_1もしくはJ_2のコピーをどちらか1部必要としている(OR要求の)場合,最適な2-ファイルスケジューリングが線形時間の手間で求められることを示す. |
| 抄録(英) | A problem of synthesizing an optimal file scheduling on a file transmission net N is to consider how to distribute, with a minimum total cost through N, copies of a file, from a vertex (start vertex) to all vertices of N by the respective vertices' copy demand numbers. Here, a file means an abstract concept of information carrier. As far, we have considered distributing one file, which is known to be NP hard in general case. This report deals with a 2 file scheduling where two different files, which we denote by J_1 and J_2, such as mail and e-mail, are distributed through N with a directed tree structure and with a constraint of vertex and arc costs. As a result, we propose a linear time algorithm to synthesize an optimal 2-file scheduling on such N where either one copy of J_1 or J_2 (OR-demand) is needed at each vertex. |
| キーワード(和) | 点コスト / 枝コスト / 点の需要値 / OR要求 / 最適な2-ファイルスケジューリング / 有向木 |
| キーワード(英) | vertex cost / arc cost / vertex demand / OR-demand / optimal 2-file scheduling / directed tree |
| 資料番号 | COMP96-51 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/12/6(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木構造のファイル複製ネットワークの最適な2 : ファイルスケジューリングについて |
| サブタイトル（和） | |
| タイトル（英） | A Synthesis of an Optimal 2-File Scheduling on a File Transmission Net |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 点コスト / vertex cost |
| キーワード(2)（和/英） | 枝コスト / arc cost |
| キーワード(3)（和/英） | 点の需要値 / vertex demand |
| キーワード(4)（和/英） | OR要求 / OR-demand |
| キーワード(5)（和/英） | 最適な2-ファイルスケジューリング / optimal 2-file scheduling |
| キーワード(6)（和/英） | 有向木 / directed tree |
| 第 1 著者 氏名（和/英） | 田内 秀和 / Hidekazu TAUCHI |
| 第 1 著者 所属（和/英） | 岐阜大学工学部電子情報工学科情報コース Dept.of Electronics and Computer Engineering, Faculty of Engineering, GIFU University |
| 第 2 著者 氏名（和/英） | 金子 美博 / Yoshihiro KANEKO |
| 第 2 著者 所属（和/英） | 岐阜大学工学部電子情報工学科情報コース Dept. of Electronics and Computer Engineering, Faculty of Engineering, GIFU University |
| 発表年月日 | 1996/12/6 |
| 資料番号 | COMP96-51 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 398 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |