A note on parallel complexity of maximum \(f\)-matching

DOI10.1016/S0020-0190(97)00196-8zbMath1338.68100MaRDI QIDQ293199

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

parallel algorithmsmaximum matching

Mathematics Subject Classification ID

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

Related Items (1)

Distributed backup placement in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• Improved processor bounds for combinatorial problems in RNC
• Parallel Merge Sort
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• On parallel complexity of maximum f-matching and the degree sequence problem
• A Short Proof of the Factor Theorem for Finite Graphs

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