| 講演名 | 2005-04-18 通信ネットワークのサイト改良による距離短縮について : 木ネットワークの場合 茨木 俊秀 /, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 通信ネットワークにおいて各サイトの性能を向上する(つまり、それに接続するリンクの伝送遅延を減らす)ことによって、ネットワークの最大距離を最小コストで指定値以下に下げる問題を考える。サイトの向上法として連続タイプと離散タイプを定義する。連続タイプでは、向上量を連続変数として扱うが、離散タイプでは一定量である。この問題は、ネットワークが一般のグラフであると、どちらのタイプもNP困難である。そこで、グラフが木である場合について、連続タイプの問題はO(|V|^2)時間で解けることを示す。しかし、離散タイプでは、グラフが線であってもやはりNP困難である。 |
| 抄録(英) | The eccentricity lowering problem is to reduce the eccentricity of a communication network within a given bound, by upgrading some nodes (i.e., shrinking the lengths of the edges linking to such nodes), where we want to minimize the required cost. We consider two types of node-upgrading strategies, i.e., the continuous upgrading and the discrete upgrading, where the improvement under the first strategy is a continuous variable, and the improvement under the second strategy is a fixed amount. These problems are NP-hard for the general graph. When the graph is a tree, we present an O(|V|^2) time algorithm to solve the eccentricity lowering problem under the continuous upgrading strategy. However, the problem under the discrete upgrading strategy is still NP-hard even if the graph is a line. |
| キーワード(和) | Communication network / eccentricity / node-upgrading / tree / line |
| キーワード(英) | Communication network / eccentricity / node-upgrading / tree / line |
| 資料番号 | COMP2005-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 通信ネットワークのサイト改良による距離短縮について : 木ネットワークの場合 |
| サブタイトル（和） | |
| タイトル（英） | Lowering Eccentricity of a Tree by Node-Upgrading |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Communication network / Communication network |
| キーワード(2)（和/英） | eccentricity / eccentricity |
| キーワード(3)（和/英） | node-upgrading / node-upgrading |
| キーワード(4)（和/英） | tree / tree |
| キーワード(5)（和/英） | line / line |
| 第 1 著者 氏名（和/英） | 茨木 俊秀 / / Toshihide IBARAKI |
| 第 1 著者 所属（和/英） | 関西学院大学理工学部 / School of Science and Technology, Kwansei Gakuin University |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-8 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 9 |
| 発行日 | |