| 講演抄録／キーワード |
| 講演名 |
2005-04-18 15:50
通信ネットワークのサイト改良による直径短縮について（木ネットワークの場合）
○茨木俊秀（関西学院大）・S.-G. ヤン（中国科学院） |
| 抄録 |
（和） |
通信ネットワークにおいて各サイトの性能を向上する(つまり、それに接続するリンクの伝送遅延を減らす）ことによって、ネットワークの最大距離を最小コストで指定値以下に下げる問題を考える。サイトの向上法として連続タイプと離散タイプを定義する。連続タイプでは、向上量を連続変数として扱うが、離散タイプでは一定量である。この問題は、ネットワークが一般のグラフであると、どちらのタイプもNP困難である。そこで、グラフが木である場合について、連続タイプの問題は $O(|V|^2)$ 時間で解けることを示す。しかし、離散タイプでは、グラフが線であってもやはりNP困難である。 |
| （英） |
The eccentricity lowering is to reduce the eccentricity of a network by upgrading some nodes (i.e., shrinking the lengthes of the edges linking to such nodes). We consider twotypes of node-upgrading strategies, i.e., the continuous upgrading strategy and the discrete upgrading strategy, 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 hard to approximate for the general graph. Therefore we restrict our attention to graphs with simple structures. We present an $O(|V|^2)$ time algorithm to solve the eccentricity lowering problem under the continuous upgrading strategy when the graph is a tree. However, we show that the problem under the discrete upgrading strategy is binary NP-hard even if the graph is a line. |
| キーワード |
（和） |
/ / / / / / / |
| （英） |
eccentricity / node upgrading / discrete upgrading strategy / continuous upgrading strategy / tree / line / convex programming / |
| 文献情報 |
信学技報, vol. 105, no. 7, COMP2005-8, pp. 57-65, 2005年4月. |
| 資料番号 |
COMP2005-8 |
| 発行日 |
2005-04-11 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|