有向グラフ上の辺素な内向木に関する最大最小定理

• Item type: SIG Technical Reports(1)
• 公開日: 2007-11-30
• タイトル: 有向グラフ上の辺素な内向木に関する最大最小定理
• タイトル / 言語: en
• タイトル: Arc-disjoint In-trees in Directed Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学院工学研究科建築学専攻
• 著者所属: 京都大学院工学研究科建築学専攻
• 著者所属: 京都大学院工学研究科建築学専攻
• 著者所属(英): en
• 著者所属(英): Department of Architecture and Architectural Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Architecture and Architectural Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Architecture and Architectural Engineering, Kyoto University
• 著者名: 神山, 直之; 加藤, 直樹; 瀧澤, 重志
• 著者名(英): Naoyuki, Kamiyama; Naoki, Katoh; Atsushi, Takizawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，｜S|＝ｄを満たす特別な点集合S＝{S1 ... Sd.｝⊆Ｖを持つ有向グラフD＝(V A) と関数 f:S→Nが与えられたとき，各 Ti ｊ が ｓｉ を根とし，ｓｉ に到達可能なVの点集合を張るような，全てのi＝1 ... dに対して、Ti 1 Ti 2... Ti ｆ(si）と表される辺素な内向木の集合が存在する必要十分条件を与える．ただし，Nは自然数の集合であるとする．この定理は，［2]によって与えられた定理，つまり特別な点S∈Vを持つ有向木D＝(V A)と自然数K∈Nが与えられたとき，虎個の辺素なVを張るsを根とする内向木が存在する必要十分条件の一般化となっている．さらに本論文では，［1]によって与えられた内向木のパッキングに関する別の特徴付けを，我々の場合へ拡張する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a directed graph D = (V,A) and a set of specified vertices S = {s1..., sd} ⊆ V with ｜S｜ = d and a function f:S 窶髏€ N where N denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σsi∈s f(si) arc-disjoint in-trees denoted by Ti,1,Ti,2,....,Ti,f(si) for every i = 1,..., d such that Ti,1,..., Ti,f(si) are rooted at Si and each Ti,j spans vertices from which si is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D = (V, A) with a specified vertex s ∈ V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 119(2007-AL-115), p. 1-8, 発行日 2007-11-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会