内向木による有向グラフの被覆

• Item type: SIG Technical Reports(1)
• 公開日: 2007-03-07
• タイトル: 内向木による有向グラフの被覆
• タイトル / 言語: en
• タイトル: Rooted Tree Covering of Directed Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: 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
• 著者名: 神山, 直之; 加藤, 直樹
• 著者名(英): Naoyuki, Kamiyama; Naoki, Katoh
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，d 個の特別な点の集合 S = {s1 ... sd} ⊆ V を持つ有向グラフ D = (V A) と関数 ?: S→Z+ ( Z+ は非負整数の集合）が与えられたとき，各Τi j がsi を根とし， si に到達可能な点集合を張り，そして全ての i = 1 … d に対するTi 1 … Ti f (si) の辺集合の合併が A を被覆するような，∑= 1 ? (si) 個の内向木の集合 {T i j : i = 1 …d j = 1 … ? (s_i) } の存在を判定する問題を考える．本論文では，この問題が重みつきマトロイド交差アルゴリズムを用いることにより， D のサイズと ∑= 1 ? (si) の多項式時間で解けることを示す．さらに，D が閉路を持たない場合は，重みつきマトロイド交差アルゴリズムの代わりに，二部グラフの最大マッチングアルゴリズムを用いることで，高速に解くことができることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider the following covering problem arising from evacuation planning problems. Given a directed graph D = (V,A) with a set of d specified vertices S = {s1,…,sd} ⊆ V and a function ﾆ驤€: S→Z+ where Z+ denotes the set of non-negative integers, our problem asks whether there exist a set of Σ=1ﾆ驤€ (si) in-trees {Ti,,j :i = 1,…, d, j = 1,,…, ﾆ驤€ (si) } such that each Ti,j is rooted at si and spans vertices from which si is reachable, and the union of all arc sets of Ti,j for i = 1,…, d and j = 1,…, ﾆ驤€ (si) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in Σ=1 ﾆ驤€ (si) and the size of D. Moreover, we prove that if D is acyclic, we can solve this problem more efficiently that general case by finding maximum matchings in a series of bipartite graphs instead of using an algorithm for the weighted matroid intersection problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 24(2008-AL-117), p. 35-42, 発行日 2007-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会