2026-04-14T22:38:46Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00031986 2025-01-22T16:23:02Z 1164:2592:2633:2637

平坦なグラフに対するコンパクトルーティング Compact Routing for Average - Case Networks 沖田, 正樹 岩間, 一雄 Masaki, Okita Kazuo, Iwama 近年，現実的なネットワークモデルを用いて伸張係数３で各頂点のルーティングテーブルサイズを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)まで削減することができる． 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). technical report 情報処理学会 2002-05-23 application/pdf 情報処理学会研究報告アルゴリズム（AL） 42(2002-AL-084) 2002 59 66 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/31986/files/IPSJ-AL02084009.pdf jpn