On parallel complexity of maximum f-matching and the degree sequence problem

DOI10.1007/3-540-58338-6_78MaRDI QIDQ5096889zbMATH OpenOpenAlexFDO

Authors Oscar Garrido, Anders Dessmark, Andrzej Lingas

Publication date 18 August 2022

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

Full work available at URL https://doi.org/10.1007/3-540-58338-6_78

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Constructing a perfect matching is in random NC
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Realizing Degree Sequences in Parallel
• Approximating matchings in parallel

Cites work

• A Las Vegas RNC algorithm for maximum matching
• A New Parallel Algorithm for the Maximal Independent Set Problem
• A Short Proof of the Factor Theorem for Finite Graphs
• Constructing a perfect matching is in random NC
• scientific article; zbMATH DE number 1256703 (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 3400923 (Why is no real title available?)
• Improved processor bounds for combinatorial problems in RNC
• Matching is as easy as matrix inversion
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• Parallel Merge Sort

Cited in

(3)

• A note on parallel complexity of maximum f-matching
• scientific article; zbMATH DE number 549852 (Why is no real title available?)
• scientific article; zbMATH DE number 562727 (Why is no real title available?)

This page was built for publication: On parallel complexity of maximum \(f\)-matching and the degree sequence problem

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