平坦なグラフに対するコンパクトルーティング

• Item type: SIG Technical Reports(1)
• 公開日: 2002-05-23
• タイトル: 平坦なグラフに対するコンパクトルーティング
• タイトル / 言語: en
• タイトル: Compact Routing for Average - Case Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学情報学研究科
• 著者所属: 京都大学情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 沖田, 正樹; 岩間, 一雄
• 著者名(英): Masaki, Okita; Kazuo, Iwama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，現実的なネットワークモデルを用いて伸張係数３で各頂点のルーティングテーブルサイズをO(n^2/3 log^4/3 n)に抑えるコンパクトルーティングアルゴリズムが提案されている[2]．この伸張係数３は一般的な下限[3]と一致し，同じモデルを用いて伸張係数３未満に制限するとテーブルサイズの上下限が(1 - o(1)) n log nまで増加してしまう具合の悪いネットワークが存在する[4]．それに対して，本稿では平均的なグラフが持つ望ましい条件として平坦性という概念を導入し，グラフが(α s γ δ)-疑似平坦である時，伸張係数s (s < 3)でテーブルサイズO((n^1-αlog n + γ n^α) log n)のコンパクトルーティングアルゴリズムを示す．特にγ を定数に定めることができるとき，テーブルサイズはO(√log n)まで削減することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In [2], Cowen presented a universal compact routing algorithm with a stretch factor of three and a table-size of O(n^2/3 log^4/3 n), based on a simple and practical model. This stretch factor of three matches a general lower bound given in [3] and also matches a much tighter lower bound if we restrict the model [4]. This paper improves these worst-case bounds by using average-vase models. The notion of it flatness is introduced for average-case netowrks. If a given network is (α, s, γ, δ)-almost-flat, then our new algorithm achieves a stretch factor of s and a table-size of O(( n^1 - α log n + γ n^α) log n).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 42(2002-AL-084), p. 59-66, 発行日 2002-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会