Processor efficient parallel matching

DOI10.1007/s00224-007-9018-5zbMath1187.68696OpenAlexW2021453140MaRDI QIDQ2471700

Piotr Sankowski

Publication date: 18 February 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9018-5

zbMATH Keywords

Parallel algorithmsFast matrix multiplicationRNC algorithmMaximum matching

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• Improved processor bounds for combinatorial problems in RNC
• High-order lifting and integrality certification
• Maximum matchings in general graphs through randomization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Classroom Note:A Simple Proof of the Leverrier--Faddeev Characteristic Polynomial Algorithm
• Faster scaling algorithms for general graph matching problems
• Nearly Optimal Algorithms for Canonical Matrix Forms
• Flow in Planar Graphs with Multiple Sources and Sinks
• Paths, Trees, and Flowers
• Algorithms – ESA 2004
• The Factorization of Linear Graphs

This page was built for publication: Processor efficient parallel matching