Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees

DOI10.1137/S0097539791195245zbMath0796.05021OpenAlexW2087311268MaRDI QIDQ4291564

Vijay V. Vazirani, H. Narayanan, Huzur Saran

Publication date: 5 September 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539791195245

zbMATH Keywords

randomization parallel algorithms arborescences matroid union edge-disjoint spanning trees linearly representable matroids

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial aspects of matroids and geometric lattices (05B35) Distributed algorithms (68W15)

Related Items (10)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Unnamed Item ⋮ A simple PTAS for weighted matroid matching on strongly base orderable matroids ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Weighted matching with pair restrictions ⋮ Linear matroid intersection is in quasi-NC ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

This page was built for publication: Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees