パンケーキグラフに対する独立木の構成方法

• Item type: SIG Technical Reports(1)
• 公開日: 2017-11-09
• タイトル: パンケーキグラフに対する独立木の構成方法
• タイトル / 言語: en
• タイトル: Independent Spanning Trees on Pancake Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 埼玉大学大学院理工学研究科数理電子情報部門
• 著者所属: 埼玉大学大学院理工学研究科数理電子情報部門
• 著者所属(英): en
• 著者所属(英): Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者名: 松井, 大地; 山田, 敏規
• 著者名(英): Daichi, Matsui; Toshinori, Yamada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: G をグラフとする．G 上の頂点 u と v を結ぶ 2 本のパス P1，P′が u と v 以外に点を共有しないならば P と P′は内点非共有であると言われる．γ をグラフ G 上の頂点とする．また，T1，T2，.... Tk を G に対する k 個の全域木とし，任意のi∈ {1, 2, ...,k} と G 上の任意の頂点 v に対して Ti 上の γ と v を結ぶ (唯一の) パスを Pi (v) で表す．G 上の任意の頂点 v に対して P1 (v)，P2 (v)， .... ，Pk (v) が内点非共有であるとき，T1，T2，... Tk は γ を根として独立であると言われる．小文では，n - パンケーキグラフに対して独立である (n - 1)個の全域木を構成する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let G be a graph, and let P and P' be two paths connecting vertices u and v on G. P and P' are said to be internally vertex-disjoint if the have no vertex in common, except u and v. Let r be a vertex in graph G. Let T₁,T₂ , ... ,Tk be k spanning trees of G, and let Pi (v) denote the (unique) path connecting r and v on Ti for any i ∈ {1, 2, ... ,k } and any vertex v of G. Z₁, T₂ , ... , Tk is said to be independent at root r if P₁ (v), P₂ (v), ... ,Pk (v) are internally vertex-disjoint for any vertex v of G. This paper constructs n — 1 independent spanning trees of an n-Pancake graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-165, 号 21, p. 1-5, 発行日 2017-11-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会