部分k木で辺素な道を見つけるアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1996-07-24
• タイトル: 部分k木で辺素な道を見つけるアルゴリズム
• タイトル / 言語: en
• タイトル: Finding Edge - Disjoint Paths in Partial k - Trees
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属(英): en
• 著者所属(英): Education Center for Information Processing, Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences, Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences, Graduate School of Information Sciences, Tohoku University
• 著者名: 周暁; 田村, 朱麗; 西関, 隆夫
• 著者名(英): Xiao, Zhou; Syurei, Tamura; Takao, Nishizeki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では部分k木Gの指定された端子対を結ぶ辺素な道を求める多項式時間アルゴリズムを3つ与える．Gの点数をnとして，端子対数をpとしたとき，最初のアルゴリズムでは，p=O(og )である限り，端子はGのどこにあってもよい．次のアルゴリズムでは端子対は何個あってもよいが，各端子対は分解木の同じ節点に入っていなければならない．これら2つを組み合せたのが3番目のアルゴリズムであり，ある条件を満足すれば端子対は必ずして分解木の同じ節点に入っていなくてもよいし，端子対がO(og )より多くてもよい．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a given graph G and p pairs (s_i,t_i), 1〓i〓p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P_i, 1〓i〓p, connecting s_i and t_i. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but it has not been known whether the edge-disjoint paths problem can be solved in polynomial time for partial k-trees unless p=O(1). This paper gives three algorithms for the edge-disjoint paths problem on partial k-trees. The first one solves the problem for any partial k-tree G and runs in polynomial time if p=O(log n) and in linear time if p=O(1) where n is the number of vertices in G. The second solves the problem for any p in polynomial time if the graph G^+ obtained from G by adding p edges (s_i,t_i), 1〓i〓p, is also a partial k-tree. The third is a combination of the first and second, and solves the edge-disjoint paths problem under some restriction even if G^+ is not always a partial k-tree and p is not always O(log n).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 67(1996-AL-052), p. 65-72, 発行日 1996-07-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会