小さい幅を持つ矩形格子への木のレイアウト

概要

論文の詳細を見る
グラフを最小点数の矩形格子にレイアウトする問題は, コンパクトなVLSIレイアウトを構成する問題や, 格子ネットワークを相互結合網として有する並列計算機システム上で効率的に計算を行なう問題の基本的な定式化であり, 盛んに研究されている.小文では, マンハッタンルーティングモデルと辺非共有ルーティングモデルの下で, 任意の2分木Tに対してTをレイアウトできる格子の最小の幅をkとするとき, 点数O((k+α)/(1+α)N), 幅k+αの格子にTを多項式時間でレイアウトできることを示す.ただし, αは0≨α≨√<N>なる任意の整数である.さらに, 与えられたグラフGと整数a, kに対して, Gが点数a, 幅kの格子にレイアウト可能か否かを判定する問題は, マンハッタンモデルの下ではGを木に制限してもNP完全であり, 辺非共有モデルの下ではGを最大次数3以下の閉路を含まないグラフに制限し, かつkを3以上の任意の定数に固定してもNP完全であることを示す.
一般社団法人電子情報通信学会の論文
2001-11-19