On mixed connectivity certificates

被引：5

作者：

Even, S ^{[1
]}

Itkis, G

Rajsbaum, S

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] NDS, IL-91235 Jerusalem, Israel

[3] Natl Autonomous Univ Mexico, Inst Matemat, Mexico City 04510, DF, Mexico

[4] Boston Univ, Boston, MA 02215 USA

[5] MIT, Comp Sci Lab, Cambridge, MA 02139 USA

[6] Digital Equipment Corp, CRL, Maynard, MA 01754 USA

来源：

THEORETICAL COMPUTER SCIENCE | 1998年 / 203卷 / 02期

基金：

美国国家科学基金会;

关键词：

connectivity certificates; mixed connectivity; distributed algorithm;

D O I：

10.1016/S0304-3975(98)00023-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

Vertex and edge connectivity are special cases of mixed connectivity, in which all edges and a specified set of vertices play a similar role. Certificates of k-connectivity for a graph are obtained by removing a subset of its edges, while preserving its connectivity up to k. We unify the previous work on connectivity certificates and extend it to handle mixed connectivity and multigraphs. Our treatment contributes a new insight of the pertinent structures, yielding more general results and simpler proofs. Also, we present the first communication-optimal distributed algorithm for finding mixed connectivity certificates. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

引用

页码：253 / 269

页数：17

共 16 条

[1]

AWERBUCH B, 1990, FOCS, P514

[2]

SCAN-1ST SEARCH AND SPARSE CERTIFICATES - AN IMPROVED PARALLEL ALGORITHM FOR K-VERTEX CONNECTIVITY [J].

CHERIYAN, J ;

KAO, MY ;

THURIMELLA, R .

SIAM JOURNAL ON COMPUTING, 1993, 22 (01) :157-174

[3]

FINDING NONSEPARATING INDUCED CYCLES AND INDEPENDENT SPANNING-TREES IN 3-CONNECTED GRAPHS [J].

CHERIYAN, J ;

MAHESHWARI, SN .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1988, 9 (04) :507-537

[4]

DANTZIG GB, 1956, ANN MATH STUD, V38, P215

[5]

Eppstein D., 1992, FOCS, P6069, DOI DOI 10.1109/SFCS.1992.267818

[6]

ON SPARSE SUBGRAPHS PRESERVING CONNECTIVITY PROPERTIES [J].

FRANK, A ;

IBARAKI, T ;

NAGAMOCHI, H .

JOURNAL OF GRAPH THEORY, 1993, 17 (03) :275-281

[7]

Gabow H.N., 1991, STOC, P112

[8]

GAREY MR, 1979, COMPUTER INTRACTABIL, P198

[9]

ITAI A, 1988, INFORM COMPUT, V79, P3

[10]

ITKIS G, 1996, UNPUB CONNECTIVITY C

← 1 2 →