完全二分木の直線埋め込みについて

スポンサーリンク

概要

論文の詳細を見る
本稿では,非縮小制約の下で歪みを小さくすることを目標とする完全二分木の直線埋め込み問題について考える.文献[8]で,MathieuとPapamanthouは,高さhの完全二分木の頂点を中間順に埋め込むことでO(2^h)の歪みで直線に埋め込めることを示した.また,現時点での直線歪み埋め込みのΩ(2^h)下界をΩ(2^h)まで大きくすることができ,O(2^h)の直線歪み埋め込みの上界が最適であると予想をしていた.本稿では,高さhの完全二分木の直線歪み埋め込み問題に対して,Θ((2^h)/h)の歪みを持つ最適な直線歪み埋め込みアルゴリズムを与える.
2010-06-18

著者

関連論文

もっと見る

スポンサーリンク