2024-03-29T20:33:56Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000322872024-03-29T05:26:34Z01164:02592:02672:02675
部分k木で辺素な道を見つけるアルゴリズムFinding Edge - Disjoint Paths in Partial k - Treesjpnhttp://id.nii.ac.jp/1001/00032287/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32287&item_no=1&attribute_id=1&file_no=1Copyright (c) 1996 by the Information Processing Society of Japan東北大学東北大学東北大学周暁田村, 朱麗西関, 隆夫本論文では部分k木Gの指定された端子対を結ぶ辺素な道を求める多項式時間アルゴリズムを3つ与える.Gの点数をnとして,端子対数をpとしたとき,最初のアルゴリズムでは,p=O(og )である限り,端子はGのどこにあってもよい.次のアルゴリズムでは端子対は何個あってもよいが,各端子対は分解木の同じ節点に入っていなければならない.これら2つを組み合せたのが3番目のアルゴリズムであり,ある条件を満足すれば端子対は必ずして分解木の同じ節点に入っていなくてもよいし,端子対がO(og )より多くてもよい.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).AN1009593X情報処理学会研究報告アルゴリズム(AL)199667(1996-AL-052)65721996-07-242009-06-30