A note on parallel complexity of maximum f-matching

DOI10.1016/S0020-0190(97)00196-8MaRDI QIDQ293199zbMATH OpenFDO

Authors Anders Dessmark, Oscar Garrido, Andrzej Lingas

Publication date 9 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001968?np=y

zbMATH Keywords

maximum matchingparallel algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Cites work

• A Las Vegas RNC algorithm for maximum matching
• A Short Proof of the Factor Theorem for Finite Graphs
• Constructing a perfect matching is in random NC
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1354126 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 1555942 (Why is no real title available?)
• Improved processor bounds for combinatorial problems in RNC
• Matching is as easy as matrix inversion
• On parallel complexity of maximum \(f\)-matching and the degree sequence problem
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• Parallel Merge Sort

Cited in

(2)

• Distributed backup placement in networks
• scientific article; zbMATH DE number 549852 (Why is no real title available?)

This page was built for publication: A note on parallel complexity of maximum \(f\)-matching

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