平面オイラーグラフ上での辺素な路問題を解く並列アルゴリズム

概要

論文の詳細を見る
Given a connected graph G=(V,E)and K pairs of vertices (s_i,t_i),i=1,..,K,the edge-disjoint path problem asks to find K pairwise edge-disjoint paths connecting each pair(s_i,t_i)from source s_i to sink t_i,=1,..,K.This problem is one of the fundamental problem in graph theory.When disjoint path problem is considered,it is convenient to introduce graph H=(V,F),called a demand graph,formed by the edges connecting each terminal pair(s_i,t_i).The original graph G=(V,E)is called the supply graph.In this paper we present a parallel algorithm to decide whether the required K edge-disjoint paths exist or not,and a parallel algorithm to find the required K edge-disjoint paths in G+H when undirected graph C+H=(V,EUF)is planar and Eulerian,and K is a constant,which run in O(log^2n)time using O(n^3)processors and in O(K(log^2n+logm))time using O(n^3+m)processors,respectively,both on a CREW PRAM,where n and m are the number of vertices and edges of G,respectively,and K is a constant.
一般社団法人情報処理学会の論文
1992-09-28