Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
From MaRDI portal
Publication:1337676
DOI10.1016/0166-218X(94)90039-6zbMath0809.90126MaRDI QIDQ1337676
Abraham P. Punnen, K. P. K. Nair
Publication date: 8 November 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
bipartite graphworst-case complexitymaximum cardinality matchingbottleneck bipartite matching problem
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (21)
A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness ⋮ The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis ⋮ Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom ⋮ Solution methods and computational investigations for the linear bottleneck assignment problem ⋮ Sensitivity analysis for bottleneck assignment problems ⋮ Bottleneck partial-matching Voronoi diagrams and applications ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ On the fast delivery problem with one or two packages ⋮ A note on the assignment problem with seniority and job priority constraints. ⋮ On bottleneck assignment problems under categorization. ⋮ Quadratic bottleneck problems ⋮ Selected topics on assignment problems ⋮ A note on the parity assignment problem ⋮ Bottleneck flows in unit capacity networks ⋮ The traveling salesman problem: new polynomial approximation algorithms and domination analysis ⋮ On a pair of job-machine assignment problems with two stages ⋮ On uniform \(k\)-partition problems ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ An improved general procedure for lexicographic bottleneck problems ⋮ Solving some lexicographic multi-objective combinatorial problems ⋮ Linear assignment procedures
Cites Work
- Unnamed Item
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Solving linear bottleneck assignment problems via strong spanning trees
- An augmenting path method for solving linear bottleneck assignment problems
- Algorithms for two bottleneck optimization problems
This page was built for publication: Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
