グラフの本型埋め込みアルゴリズムについて
スポンサーリンク
概要
- 論文の詳細を見る
グラフの本型埋め込みとは、各ノードは本の背上にあり、各辺は本のページ上にどの任意の辺同士も共通のノード以外ではお互いに交差しないように埋め込まれた埋め込みのことである.AtneosenやBernhartとKainenはそれぞれ独立に、各辺がページを跨って埋め込むことができるとき、任意のグラフは3ページの本型に埋め込むことができることを証明した.しかし彼らの方法をもとに得られる埋め込みアルゴリズムの時間計算量はnノードの完全グラフに対して少なくともΩ(n)必要となることがわかる.著者は以前にO(mn)となるアルゴリズムを示した.本論文ではこの結果を改良し、ノード数n辺数mのグラフに対し新たにO(m log n)の時間計算量をもつアルゴリズムを示す.
- 社団法人電子情報通信学会の論文
- 1994-09-22
著者
関連論文
- グラフの辺が本の背と ⌈m log_d n⌉ の交差数をもつd+1ページ本型への埋蔵
- グラフの辺が本の背とO(m log_dn)の交差数をもつd+1ページ本型への埋蔵
- グラフの本型埋め込みアルゴリズムについて
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (信号処理)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (通信方式)
- 2部グラフの細分のスタックキューミックスレイアウトの構成 (回路とシステム)