4連結平面グラフを4分割する線型時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1996-09-13
• タイトル: 4連結平面グラフを4分割する線型時間アルゴリズム
• タイトル / 言語: en
• タイトル: A Linear - Time Algorithm for Four - Partitioning Four - Connected Planar Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: 中野, 眞一; ラハマンモハマドサイドゥル; 西関, 隆夫
• 著者名(英): Shin-Ichi, Nakano; Md., SaidurRahman; Takao, Nishizeki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフG=(，)，4点u_1，u_2，u_3，u_4∈VおよびΣ^4_<i=1> n_i=|V|なる4つの自然数n_1，n_2，n_3，n_4が与えられたとき、各i，1〓i〓4についてu_i∈V_i，|V_i|=n_iかつV_iによるGの誘導部分グラフが連結であるようなVの4分割V_1，V_2，V_3，V_4を求めたい。本論文では、Gが4連結平面グラフ、かつu_1，u_2，u_3，u_4がGのひとつの面上にあるとき、上記の4分割を求める線型時間アルゴリズムを与える。我々のアルゴリズムはGの4正規分割を用いている。4正規分割はグラフ描画の分野で知られているst順序付けや正規4順序付けの一般化である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a graph G = (V,E), four distinct vertices u_1, u_2, u_3, u_4 ∈ V and four natural numbers n_1, n_2, n_3, n_4 such that Σ^4_<i=1> n_i=|V|, we wish to find a partition V_1, V_2, V_3, V_4 of the vertex set V such that u_i ∈ V_i,|V_i|=n_i and V_i induces a connected subgraph of G for each i, 1〓i〓4. In this paper we give a simple linear-time algorithm to find such a 4-partition of G if G is a 4-connected planar graph and u_1, u_2, u_3, u_4 are located on the same face of G. Our algorithm is based on a "4-canonical decomposition" of G, which is a generalization of an st-numbering and a "canonical 4-ordering" known i the area of graph drawings.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 89(1996-AL-053), p. 7-14, 発行日 1996-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会