総頂点間経路長を最小にするサイクルグラフヘの１辺追加

• Item type: SIG Technical Reports(1)
• 公開日: 2007-05-17
• タイトル: 総頂点間経路長を最小にするサイクルグラフヘの１辺追加
• タイトル / 言語: en
• タイトル: Adding an Edge to a Cycle Graph Minimizing Total Path Length
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 流通科学大学情報学部経営情報学科
• 著者所属: 流通科学大学情報学部経営情報学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Management Science, Faculty of Information Science, University of Marketing and Distribution Sciences
• 著者所属(英): en
• 著者所属(英): Department of Information and Management Science, Faculty of Information Science, University of Marketing and Distribution Sciences
• 著者名: 澤田, 清; 中西, 朗裕
• 著者名(英): Kiyoshi, SAWADA; Akihiro, NAKANISHI
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では、頂点数 L のサイクルグラフに１辺を追加する場合について、総頂点間経路長を最小にする辺追加位置を求める。辺を追加する２頂点の大きくない方の経路長を M としたとき、総頂点間経路長を最小にする M* は、L が奇数のとき M*＝L-1/2、L が４の倍数のとき M*＝L/2、L が４の倍数でない偶数のとき M*＝L/2－１ となった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a problem of adding an edge to a cycle graph with L nodes. When M indicates the shortest path length before adding the edge between two nodes which are incident with the additional edge, the optimal M* is obtained by minimizing the total path length which is the sum of shortest path lengths between every pair of all nodes. If L is a odd number, then M* = L-1/2. If L is a multiple of four, then M* = L/2. If L is a even number and is not a multiple of four, then M* = L/2 - 1.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 2007, 号 43(2007-MPS-064), p. 33-36, 発行日 2007-05-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会