A Las Vegas RNC algorithm for maximum matching

DOI10.1007/BF02579264zbMath0646.05050OpenAlexW2011594074MaRDI QIDQ1103637

Howard J. Karloff

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579264

zbMATH Keywords

algorithmsmaximum matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

A note on parallel complexity of maximum \(f\)-matching ⋮ Matching is as easy as matrix inversion ⋮ Approximating weighted matchings in parallel ⋮ Constructing a perfect matching is in random NC ⋮ Parallel \((\Delta +1)\)-coloring of constant-degree graphs ⋮ Designing checkers for programs that run in parallel ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ On parallel complexity of maximum f-matching and the degree sequence problem ⋮ Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems ⋮ Independent sets versus perfect matchings ⋮ Processor efficient parallel matching ⋮ SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS

Cites Work

• Constructing a perfect matching is in random NC
• Min-max Relations for Directed Graphs
• Paths, Trees, and Flowers
• On the structure of factorizable graphs