PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS

DOI10.1142/S0129054193000122MaRDI QIDQ4286119zbMATH OpenOpenAlexFDO

Authors Krzysztof Diks, Oscar Garrido, Andrzej Lingas

Publication date 27 March 1994

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054193000122

zbMATH Keywords

EREW PRAMmaximal \(f\)-matchingmaximal independent setNC algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• An optimal parallel algorithm for maximal matching
• An improved parallel algorithm for maximal matching
• Using maximal independent sets to solve problems in parallel
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Approximating matchings in parallel

Cited in

(5)

• Fast primal-dual distributed algorithms for scheduling and matching problems
• A note on parallel complexity of maximum f-matching
• On parallel complexity of maximum \(f\)-matching and the degree sequence problem
• The maximal f-dependent set problem for planar graphs is in NC
• A simple randomized parallel algorithm for maximal f-matchings

This page was built for publication: PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS

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