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

DOI10.1007/3-540-58338-6_78zbMATH Open1493.68264OpenAlexW1853868098MaRDI QIDQ5096889FDOQ5096889

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

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

Mathematics Subject Classification ID

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

Cites Work

• Constructing a perfect matching is in random NC
• Title not available (Why is that?)
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Improved processor bounds for combinatorial problems in RNC
• Parallel Merge Sort
• Title not available (Why is that?)
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• A Short Proof of the Factor Theorem for Finite Graphs
• Title not available (Why is that?)
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Title not available (Why is that?)

Cited In (3)

• A note on parallel complexity of maximum \(f\)-matching
• Title not available (Why is that?)
• Title not available (Why is that?)

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)