Shortest augmenting paths for online matchings on trees
type: Item
instance of: scholarly article
title: Shortest augmenting paths for online matchings on trees
zbMATH Open document ID: 1390.68768
author: Bartłomiej Bosek
author: Dariusz Leniowski
author: Piotr Sankowski
author: Anna Zych-Pawlewicz
published in: Theory of Computing Systems
publication date: 2018-04-12T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6859224
zbMATH Keywords: online matchings
zbMATH Keywords: bipartite matchings
zbMATH Keywords: approximate matchings
zbMATH Keywords: shortest augmenting paths
zbMATH Keywords: dynamic graph algorithms
MaRDI profile type: Publication
full work available at URL: s00224-017-9838-x
OpenAlex ID: W2787900023
cites work: Fully Dynamic Maximal Matching in O (log n) Update Time
cites work: Fully Dynamic Matching in Bipartite Graphs
cites work: Constructing a perfect matching is in random NC
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Online perfect matching and mobile computing
cites work: Maintaining Assignments Online: Matching, Scheduling, and Flows
cites work: Dynamic Approximate Vertex Cover and Maximum Matching
cites work: AdWords and generalized online matching
cites work: Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
cites work: Q2934589
cites work: A data structure for dynamic trees
DOI: 10.1007/S00224-017-9838-X
Recommended article: Shortest Augmenting Paths for Online Matchings on Trees
Recommended article: A tight bound for shortest augmenting paths on trees
Recommended article: On improving matchings in trees, via bounded-length augmentations
Recommended article: On-line matching routing on trees
Recommended article: Maximum matching on trees in the online preemptive and the incremental graph models
Recommended article: Maximum matching on trees in the online preemptive and the incremental dynamic graph models
Recommended article: Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
Recommended article: Optimal Bounds for Matching Routing on Trees
Recommended article: Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length
description: scientific article; zbMATH DE number 6859224