本型空間への2部グラフの埋蔵
スポンサーリンク
概要
- 論文の詳細を見る
グラフの本型空間への埋め込みとは,各頂点は本の背上にあり,各辺は本のページ上にどの任意の辺同士も共通の頂点以外ではお互いに交差しないように埋め込まれた埋め込みのことである.ここでは辺は背をまたがって複数ページに埋蔵可能であるという条件のもとでの考察をおこなう.このとき任意のグラフに対し,3ページあれば必ず本型埋め込みが可能であることが既に知られている.以前に,頂点数n,辺数mの一般のグラフに対し本の背とグラフの辺との交差数がO(m log_dn)となるようなd+1ページヘの埋蔵方法を示した.さらに本結果はオーダに関しては最善であることも示した.本論文ではそれぞれm頂点と,n頂点(m>n)からなる2個の部分グラフを持つ2部グラフG_<m,n>に対して検討をし,この埋蔵方法を改良して交差数を減らし,任意の2部グラフG_<m,n>に対して,本の背とグラフの各辺との交差数が〓log_dn〓となるようなd+1ページヘの本型埋め込みを示した.本結果は最高次数の係数に関して最善だと予想している.
- 社団法人電子情報通信学会の論文
- 2004-06-18
著者
関連論文
- 多種球充填
- 多種球充填II
- 単色辺からなるグラフのトラックレイアウト(一般,ネットワーク,通信のための信号処理及び一般)
- 単色辺からなるグラフのトラックレイアウト(一般,ネットワーク,通信のための信号処理及び一般)
- 単色辺からなるグラフのトラックレイアウト(一般,ネットワーク,通信のための信号処理及び一般)
- アダマール行列の一般化とその応用
- 2部グラフの細分の(d,3)トラックレイアウト
- 2部グラフの細分のトラックレイアウトの改良
- 2部グラフの細分のスタックキューミックスレイアウト(グラフ,ペトリ,ニューラルネット及び一般)
- 2部グラフの細分のスタックキューミックスレイアウト(グラフ,ペトリ,ニューラルネット及び一般)
- 2部グラフの細分のスタックキューミックスレイアウト
- 2部グラフの細分のトラックレイアウト
- 2部グラフの細分のキューレイアウト
- 本型空間への2部グラフの埋蔵
- 多種球充填II
- 多種球充填モデル
- 多種球充填モデルとその応用例
- 2部グラフの細分のスタックキューミックスレイアウトの構成(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 2部グラフの細分のスタックキューミックスレイアウトの構成(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 2部グラフの細分のスタックキューミックスレイアウトの構成(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフのキューレイアウトの改良(システムと信号処理及び一般)
- グラフのキューレイアウトの改良(システムと信号処理及び一般)
- グラフのキューレイアウトの改良(システムと信号処理及び一般)
- グラフのキューレイアウトの改良(システムと信号処理及び一般)
- 球疎充填シミュレーションモデルとその充填密度近似公式
- グラフのスタックキューミックスレイアウトの改良(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフのスタックキューミックスレイアウトの改良(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフのスタックキューミックスレイアウトの改良
- グラフのスタックキューミックスレイアウトの改良
- 球充填シミュレーション高速アルゴリズム
- グラフの細分のスタックキューミックスレイアウト(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフの細分のスタックキューミックスレイアウト(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)