Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems

DOI10.1016/0020-0190(91)90173-FzbMath0748.68027OpenAlexW2012515371MaRDI QIDQ1183464

Joel M. Wein

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90173-f

zbMATH Keywords

perfect matching\(T\)-join problemLas Vegas RNC algorithmparallel complexity of matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items

Dense open-shop schedules with release times, Two-stage open shop scheduling with a bottleneck machine

Cites Work

• Matching theory
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• Finding thet-join structure of graphs
• Finding Minimum-Cost Circulations by Successive Approximation
• On Odd Cuts and Plane Multicommodity Flows
• 2-Matchings and 2-covers of hypergraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item