Minimizing maximum weight of subsets of a maximum matching in a bipartite graph

DOI10.1016/J.DAM.2015.01.008MaRDI QIDQ499331zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmbipartite graphnon-approximabilitymaximal matchingNP-hardness in the strong sense

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• 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
• Assignment Problems
• Determining crane areas in intermodal transshipment yards: the yard partition problem
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

Cited in

(10)

• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
• Crossing minimization in weighted bipartite graphs
• A weighted perfect matching with constraints on weights of its parts
• Scheduling dedicated jobs with variative processing times
• Solving the single crane scheduling problem at rail transshipment yards
• Bottleneck subset-type restricted matching problems
• Crossing Minimization in Weighted Bipartite Graphs
• Socially fair matching: exact and approximation algorithms
• The partitioning min-max weighted matching problem
• Optimum matchings in weighted bipartite graphs

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)