An optimal parallel algorithm for maximal matching

DOI10.1016/0020-0190(94)90130-9zbMath0823.68040OpenAlexW1998998849MaRDI QIDQ1341686

Pierre Kelsen

Publication date: 9 January 1995

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90130-9

zbMATH Keywords

parallel algorithmmaximal matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (8)

A fast and efficient NC algorithm for maximal matching ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ A simple randomized parallel algorithm for maximal f-matchings ⋮ An improvement on parallel computation of a maximal matching ⋮ An efficient parallel graph edge matching algorithm and its applications ⋮ An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs

Cites Work

• An improved parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Constructing a Maximal Independent Set in Parallel
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An optimal parallel algorithm for maximal matching