Online Matching in Regular Bipartite Graphs

DOI10.1142/S0129626418500081zbMath1490.68301OpenAlexW2809638413MaRDI QIDQ5087843

Janosch Fuchs, Xavier Muñoz, Walter Unger, Lali Barrière

Publication date: 4 July 2022

Published in: Parallel Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129626418500081

zbMATH Keywords

bipartite graphmatchingcompetitive ratioonline algorithmadvice complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items

Online Matching in Regular Bipartite Graphs with Randomized Adversary

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the advice complexity of online bipartite matching and online stable marriage
• AdWords and generalized online matching
• Randomized online algorithms for minimum metric bipartite matching
• Online Computation with Advice
• On the Advice Complexity of Online Problems
• Online Weighted Matching
• Online Stochastic Matching: Beating 1-1/e
• Online bipartite matching with random arrivals
• How Much Information about the Future Is Needed?