test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works
       

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9471

Title: Splitting an Expander Graph
Authors: Molloy, M.
Frieze, A.
Issue Date: 1999
Publisher: Elsevier
Citation: Frieze, A. M., & Molloy, M. (1999). Splitting an expander graph. Journal of Algorithms, 33(1), 166-172.
Abstract: 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=E1∪E2∪···∪Ek so that the graphs Gi=(V,Ei) 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).
Description: Homepage for the Journal of Algorithms http://www.sciencedirect.com/science/journal/01966774
URI: http://hdl.handle.net/1807/9471
ISSN: 0196-6774
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
splitting an expander graph.pdf163.2 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

uoft