Processor efficient parallel matching

DOI10.1007/S00224-007-9018-5MaRDI QIDQ2471700zbMATH OpenOpenAlexFDO

Authors 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

Fast matrix multiplicationMaximum matchingParallel algorithmsRNC algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 43583
• Approximating matchings in parallel
• Optimal parallel algorithms for Prefix Matching
• scientific article; zbMATH DE number 4084974
• scientific article; zbMATH DE number 4049127
• Parallel Algorithms for Term Matching
• An optimal parallel algorithm for maximal matching
• Parallel algorithms for combinatorial pattern matching
• Publication:4206393

Cites work

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

Cited in

(4)

• Constructing a perfect matching is in random NC
• Improved processor bounds for combinatorial problems in RNC
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• NC algorithms for weighted planar perfect matching and related problems

This page was built for publication: Processor efficient parallel matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2471700)