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

DOI10.1142/S0129054193000122zbMath0802.68092OpenAlexW2066480089MaRDI QIDQ4286119

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

maximal independent setEREW PRAMNC algorithmsmaximal \(f\)-matching

Mathematics Subject Classification ID

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

Related Items (5)

A note on parallel complexity of maximum \(f\)-matching ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ 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