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

DOI10.1007/3-540-58338-6_78zbMath1493.68264OpenAlexW1853868098MaRDI QIDQ5096889

Oscar Garrido, Andrzej Lingas, Anders Dessmark

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

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

Related Items (1)

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

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
• A New Parallel Algorithm for the Maximal Independent Set Problem
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• A Short Proof of the Factor Theorem for Finite Graphs

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