@techreport{oai:ipsj.ixsq.nii.ac.jp:00031986,
 author = {沖田, 正樹 and 岩間, 一雄 and Masaki, Okita and Kazuo, Iwama},
 issue = {42(2002-AL-084)},
 month = {May},
 note = {近年，現実的なネットワークモデルを用いて伸張係数３で各頂点のルーティングテーブルサイズを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).},
 title = {平坦なグラフに対するコンパクトルーティング},
 year = {2002}
}