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

Authors
NARAYANAN H SARAN H VAZIRANI VV
Citation
H. Narayanan et al., RANDOMIZED PARALLEL ALGORITHMS FOR MATROID UNION AND INTERSECTION, WITH APPLICATIONS TO ARBORESENCES AND EDGE-DISJOINT SPANNING-TREES, SIAM journal on computing, 23(2), 1994, pp. 387-397
Citations number
28
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
2
Year of publication
1994
Pages
387 - 397
Database
ISI
SICI code
0097-5397(1994)23:2<387:RPAFMU>2.0.ZU;2-R
Abstract
The strong link between matroids and matching is used to extend the id eas that resulted in the design of random NC (RNC) algorithms for matc hing to obtain RNC algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a cons equence, RNC algorithms for the well-known problems of finding an arbo rescence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and ra ndomization.