A Parallel Algorithm for 2-Edge-Connectivity Augmentation of a Connected Graph with Multipartition Constraints

摘要

The k-edge-connectivity augmentation problem with multipartition constraints (kECAM for short) is defined by ȁC;Given an undirected graph G = (V, E) and a multipartition π = {V1,..., Vr} of V with Vi Ȣ9; Vj = Ƞ5; for Ƞ0;i, j Ƞ8; {1,..., r} (i Ȧ0; j), find an edge set E'' of minimum cardinality, consisting of edges that connect distinct members of π, such that G'' = (V, EȢA;E'') is k edge-connected.ȁD; In this paper, we propose a parallel algorithm, running on an EREW PRAM, for finding a solution to 2ECAM when G is connected. The main idea is to reduce 2ECAM to the bipartition case, that is, 2ECAM with r = 2.