文献

J-GLOBAL ID：201402293074667316   整理番号：14A0569349

底辺付き極大平面グラフの定数時間遅延列挙

Constant-time Delay Generation of Based Plane Triangulations

著者 (4件)： KOIDE Jun-ichi (Iwate Univ., Tokyo, JPN) ,  YAMANAKA Katsuhisa (Iwate Univ., Tokyo, JPN) ,  HIRAYAMA Takashi (Iwate Univ., Tokyo, JPN) ,  NISHITANI Yasuaki (Iwate Univ., Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 488(COMP2013 60-73)  ページ： 91-98  発行年： 2014年03月03日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 全ての面が三角形である平面グラフを極大平面グラフという。極大平面グラフの外周上の1辺を底辺として指定したグラフを底辺付き極大平面グラフという。本稿では,ちょうどm面をもつ2連結底辺付き極大平面グラフを列挙するアルゴリズムを与える。李と中野[9]により,高々n頂点をもつ2連結底辺付き極大平面グラフを1つ当たり定数時間で列挙するアルゴリズムがすでに提案されている。彼らのアルゴリズムを改良することによって,ちょうどm面をもつ2連結底辺付き極大平面グラフを列挙することができる。このアルゴリズムの遅延時間はO(m)である。ここで,遅延時間とは連続した2つの出力間の計算時間である。これに対し,提案するアルゴリズムは,m面をもつ2連結底辺付き極大平面グラフを定数時間遅延で列挙する。すなわち,任意の連続した2つの出力間の計算時間が定数で抑えられる。我々のアルゴリズムはAvisと福田[5]によって提案された逆探索法に基づいている。(著者抄録)

シソーラス用語： *底面 ,  *平面グラフ ,  *定数 ,  *遅れ ,  三角形 ,  *極大値 ,  アルゴリズム ,  CPU時間 ,  検出アルゴリズム
準シソーラス用語： *時間遅延

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (10件)：

• L.C. Aleardi, O. Devillers, and G. Schaeffer. Succinct representation of triangulations with a boundary. Proc. 9th Workshop on Algorithms and Data Structures (WADS 2005), LNCS 3608:134-145, 2005.
• L.C. Aleardi, O. Devillers, and G. Schaeffer. Succinct representations of planar maps. Theoretical Computer Science, 408:174-187, 2008.
• H. Arimura and T. Uno. An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence. Journal of Combinatorial Optimization, 13, 2007.
• D. Avis. Generating rooted triangulations without repetitions. Algorithmica, 16:618-632, 1996.
• D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1-3):21-46, 1996.

タイトルに関連する用語 (3件)： 平面グラフ ,  定数 ,  時間遅延