Record Details

RANDOMIZED PARALLEL ALGORITHMS FOR MATROID UNION AND INTERSECTION, WITH APPLICATIONS TO ARBORESENCES AND EDGE-DISJOINT SPANNING-TREES

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title RANDOMIZED PARALLEL ALGORITHMS FOR MATROID UNION AND INTERSECTION, WITH APPLICATIONS TO ARBORESENCES AND EDGE-DISJOINT SPANNING-TREES
 
Creator NARAYANAN, H
SARAN, H
VAZIRANI, VV
 
Subject parallel algorithms
randomized algorithms
graph algorithms
matroids
 
Description The strong link between matroids and matching is used to extend the ideas that resulted in the design of random NC (RNC) algorithms for matching to obtain RNC algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a consequence, RNC algorithms for the well-known problems of finding an arborescence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and randomization.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:38:59Z
2011-12-26T12:58:26Z
2011-12-27T05:48:22Z
2011-08-29T05:38:59Z
2011-12-26T12:58:26Z
2011-12-27T05:48:22Z
1994
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 23(2), 387-397
0097-5397
http://dx.doi.org/10.1137/S0097539791195245
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11980
http://hdl.handle.net/10054/11980
 
Language en