パス幅が限られたグラフの族に対する普遍グラフ

• Item type: SIG Technical Reports(1)
• 公開日: 1991-11-22
• タイトル: パス幅が限られたグラフの族に対する普遍グラフ
• タイトル / 言語: en
• タイトル: Universal Graphs for Graphs with Bounded Path - Width
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学電気電子工学科
• 著者所属: 東京工業大学電気電子工学科
• 著者所属: 東京工業大学電気電子工学科
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Electronic Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Electronic Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Electronic Engineering Tokyo Institute of Technology
• 著者名: 高橋, 篤司; 上野, 修一; 梶谷, 洋司
• 著者名(英): Atsushi, Takahashi; Shuichi, Ueno; Yoji, Kajitani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの族Fに属すすべてのグラフを部分グラフとして含むグラフをFに対する普遍グラフという．Fに対する枝数最小の普遍グラフは最小普遍グラフと呼ばれる．小文ではパス幅が高々kかつn点上のグラフの族F^k_nに対する最小普遍グラフについて考察する．まず，F^k_nに対する普遍グラフの枝数は少なくともΩ( log n/）であることを示す．次に，Fに対する枝数O（ n log n/）の普遍グラフを構成し，最小普遍グラフの枝数はΘ（ n log n/）であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. The minimum universal graph for is a universal graph for F with the minimum number of edges. This paper considers the minimum universal graph for the family F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graphs for F^k_n is at least Ω(k n log_^n_k). Next, we construct a universal graph for F^k_n with O(k n log^n_k) edges, and show that the number of edges in the minimum universal graph F^k_n is Θ(kn log^n_k).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1991, 号 102(1991-AL-024), p. 1-8, 発行日 1991-11-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会