Sublinear-Time Parallel Algorithms for Matching and Related Problems

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.1006/JAGM.1993.1009" rel="nofollow">DOI 10.1006/JAGM.1993.1009</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/0769.68034" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W2064306958" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q4033764" rel="nofollow">MaRDI QID Q4033764</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q4033764" rel="nofollow">FDO</a>

Authors Andrew V. Goldberg, Pravin M. Vaidya, Serge Plotkin

Publication date 16 May 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1993.1009

zbMATH Keywords

depth-first searchbipartite matchingminimum-cost flowflows in zero-one networksmaximal node-disjoint pathssublinear-time deterministic parallel algorithms

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Distributed algorithms (68W15)

Recommendations

• An optimal parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
• Faster scaling algorithms for general graph matching problems
• scientific article; zbMATH DE number 1003296

Cited in

(16)

• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
• An adjustable linear time parallel algorithm for maximum weight bipartite matching
• A faster parameterized algorithm for temporal matching
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• Approximate labelled subtree homeomorphism
• Sublinear Algorithms for Parameterized Matching
• Fast Interior Point Methods for Bipartite Matching
• Algorithms and codes for dense assignment problems: The state of the art
• An efficient cost scaling algorithm for the assignment problem
• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On efficient implicit OBDD-based algorithms for maximal matchings
• An efficient parallel graph edge matching algorithm and its applications

This page was built for publication: Sublinear-Time Parallel Algorithms for Matching and Related Problems

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