An 0(n log n) algorithm for the convex bipartite matching problem
type: Item
instance of: scholarly article
title: An 0(n log n) algorithm for the convex bipartite matching problem
zbMATH Open document ID: 0537.90091
DOI: 10.1016/0167-6377(84)90068-3
author: N. E. Zubov
published in: Operations Research Letters
publication date: 1984-01-01T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3854828
zbMATH Keywords: maximum cardinality matching problem
zbMATH Keywords: convex bipartite graphs
zbMATH Keywords: special data structure
zbMATH Keywords: binary heap
MaRDI profile type: Publication
full work available at URL: 0167-6377(84)90068-3
OpenAlex ID: W2043765170
cites work: Maximum matching in a convex bipartite graph
cites work: Q4057549
cites work: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
cites work: Q3707420
Recommended article: A linear time algorithm for maximum matchings in convex, bipartite graphs
Recommended article: An efficient algorithm for the bipartite matching problem
Recommended article: An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
Recommended article: Q4252363
Recommended article: On the computational complexity of the bipartizing matching problem
Recommended article: A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
Recommended article: A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
Recommended article: A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
Recommended article: Approximation algorithms for bipartite matching with metric and geometric costs
Recommended article: A near-linear time ε-approximation algorithm for geometric bipartite matching
description: scientific article; zbMATH DE number 3854828