平面グラフの共通面埋め込み問題とその応用

• Item type: SIG Technical Reports(1)
• 公開日: 1999-03-15
• タイトル: 平面グラフの共通面埋め込み問題とその応用
• タイトル / 言語: en
• タイトル: Common - face Embeddings of Planar Graphs with Applications
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京電機大学理工学部数理学科
• 著者所属: SUNY at Buffalo
• 著者所属: Yale University
• 著者所属(英): en
• 著者所属(英): Tokyo Denki Univesity
• 著者所属(英): en
• 著者所属(英): SUNY at Buffalo
• 著者所属(英): en
• 著者所属(英): Yale University
• 著者名: 陳致中; Xin, He; Ming-YangKao
• 著者名(英): Zhi-Zhong, Chen; Xin, He; Ming-Yang, Kao
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面グラフG＝（V，E）と列C_1，．．．，Cq（各C_iはVの部分集合の族の列）が与えられたとき、Gの平面への埋め込みの中から、各C_iに対してある面F_iの境界がC_iに属する各集合と空ではない共通部分を持つようなものを求めたい。この問題がNP困難であることを示す。主な結果は、各C_iに属する各集合がGの連結である部分グラフを導出するという制限を加えた場合、この問題を解くO（αlogα）?時間のアルゴリズムを設計できたことである（αは入力のサイズ）。この特別な場合の問題はトポロジカル推論やVLSI設計などへの応用がある。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a planar graph g and a sequence C_1...,C_q, where each C_i is a family of vertex subsets of g we wish to find a plane embedding of g such that for each i ∈{1,...,q}, there is a face F_i in the embedding whose boundary intersects every set in C_i. We show that this problem is NP-complete. Our main result is an O(αlogα)-time(αis the input size) algorithm for an important special case where for each input family C_i induces a connected subgraph of the input graph g. This special case naturally arises from topological inference and VLSI problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1999, 号 26(1998-AL-067), p. 7-14, 発行日 1999-03-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会