2部グラフの細分のスタックキューミックスレイアウトの構成(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)

概要

論文の詳細を見る
グラフGがs-スタックq-キューミックスレイアウトを持つとは,Gがある共通の頂点順序により定義されているs個のスタックとq個のキューを持ち,Gの各辺はある1つのスタックかある1つのキューに属するようなレイアウトを持つことをいう.グラフの細分のスタックキューミックスレイアウトについては,任意のグラフGに対し各辺が4「log_<(s+q)q>sn(G)」(あるいは2+4「log_<(s+q)q>q^n(G)」個の細分点を持つGの細分のs-スタックq-キューミックスレイアウトが存在することがDujmovicとWoodによって示された.ここでsn(G)はGのスタック数,qn(G)はGのキュー数である.本論文では完全2部グラフに対してこの結果を改良し,m頂点,n頂点(m≧n)からなる2個の部集合を持つ任意の完全2部グラフK_<m,n>に対して,各辺が2「log_<(s+q)q>n」-1個の細分点を持つK_<m,n>の細分のs-スタックq-キューミックスレイアウトを構成する方法を示す.
2011-02-24