Splitting an expander graph

被引：18

作者：

Frieze, AM ^{[1
]}

Molloy, M

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[2] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 3G4, Canada

来源：

JOURNAL OF ALGORITHMS | 1999年 / 33卷 / 01期

基金：

加拿大自然科学与工程研究理事会; 美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1999.1023

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let G = (V, E) be an r-regular expander graph. Certain algorithms for finding edge disjoint paths require that its edges be partitioned into E = E-1 boolean OR E-2 boolean OR ...boolean OR E, so that the graphs G(i) = (V, E-i) are each expanders. In this paper we give a nonconstructive proof of the existence a very good split plus an algorithm for finding a partition better than that given in A. Z. Broder, A. M. Frieze, and E. Upfal (SIAM J. Comput. 23 (1994), 976-989). (C) 1999 Academic Press.

引用

页码：166 / 172

页数：7

共 10 条

[1]

ALON N, 1991, RANDOM STRUCT ALGORI, V2, P366

[2]

ALON N, 1992, PROBABILISTIC METHOD

[3] AN ALGORITHMIC APPROACH TO THE LOVASZ LOCAL LEMMA .1. [J].

BECK, J .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :343-365

[4] EXISTENCE AND CONSTRUCTION OF EDGE-DISJOINT PATHS ON EXPANDER GRAPHS [J].

BRODER, AZ ;

FRIEZE, AM ;

UPFAL, E .

SIAM JOURNAL ON COMPUTING, 1994, 23 (05) :976-989

[5]

Knuth D. E., 1968, The Art of Computer Programming, Volume I: Fundamental Algorithms, VI

[6]

LEIGHTON T, 1996, P WORKSH RAND PAR CO

[7]

LEIGHTON T, P SODA 99

[8]

LEIGHTON T, 1998, P HAW INT C SYST SCI

[9]

Molloy M., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P524, DOI 10.1145/276698.276866

[10]

[No title captured]

← 1 →