Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
DOI10.1016/J.DAM.2015.01.008zbMATH Open1321.05198OpenAlexW1965881248MaRDI QIDQ499331FDOQ499331
Maksim Barketau, Erwin Pesch, Y. Shafransky
Publication date: 30 September 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.01.008
Recommendations
- An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
- A weighted perfect matching with constraints on weights of its parts
- Theory and Applications of Models of Computation
- An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
- The partitioning min-max weighted matching problem
approximation algorithmbipartite graphnon-approximabilitymaximal matchingNP-hardness in the strong sense
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Assignment Problems
- Title not available (Why is that?)
- Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem
- Determining crane areas in intermodal transshipment yards: the yard partition problem
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Algorithm for the solution of the bottleneck assignment problem
- An augmenting path method for solving linear bottleneck assignment problems
Cited In (10)
- Scheduling dedicated jobs with variative processing times
- An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
- Socially fair matching: exact and approximation algorithms
- Optimum matchings in weighted bipartite graphs
- Crossing Minimization in Weighted Bipartite Graphs
- Bottleneck subset-type restricted matching problems
- The partitioning min-max weighted matching problem
- A weighted perfect matching with constraints on weights of its parts
- Crossing minimization in weighted bipartite graphs
- Solving the single crane scheduling problem at rail transshipment yards
This page was built for publication: Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499331)
