グラフのトラックレイアウト構成方法のアルゴリズム的表現

• Item type: SIG Technical Reports(1)
• 公開日: 2014-06-06
• タイトル: グラフのトラックレイアウト構成方法のアルゴリズム的表現
• タイトル / 言語: en
• タイトル: Algorithmic construction of track layouts of graph subdivisions
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電信電話株式会社ＮＴＴコミュニケーション科学基礎研究所
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者名: 宮内, 美樹
• 著者名(英): Miki, Miyauchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 2 部グラフの細分のトラックレイアウトについては，以前に著者が，m 頂点，n 頂点 (m≧n) からなる部集合を持つ任意の 2 部グラフ Gm,n に対して，各辺が 「logｄ n ]-1 個の細分点を持つ Gm,n の細分の (d,3) - トラックレイアウトが存在することを示した．本論文では，今までは説明文で書いていた数字列集合に対する幅優先順序を，新たにリカーシブに定義できることを示した．さらに各細分辺のトラック割り当てへのアルゴリズムを簡潔にすることにより，全体としてトラックレイアウトの構成方法をよりアルゴリズム的に書き下すことに成功した．これにより，従来はトポロジカルな問題としてとらえられていた，グラフのトラックレイアウトの問題が，アルゴリズム研究のトピックとしても面白い問題であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper studies the problem of track layout of bipartite graph subdivisions. Previously the author shows that for every integer d ≧ 2, every bipartite graph Gm,n (m≧n) has a (d,3)-track subdivision with [logd n]-1 division vertices per edge. This paper rewrites the construction proof from the algorithmic approach. By showing the construction algorithmically, the author insists that track layout problems of graphs also become an interesting problem from the aspect of algorithmic research as well as topological graph theory.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-148, 号 5, p. 1-6, 発行日 2014-06-06
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会