A weighted perfect matching with constraints on weights of its parts

DOI10.33048/DAIO.2021.28.667MaRDI QIDQ5100129zbMATH OpenOpenAlexFDO

Authors Oleg Duginov

Publication date 29 August 2022

Published in Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/da1279

zbMATH Keywords

assignment problemNP-hardnessperfect matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• An unfeasible matching problem
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Optimum matchings in weighted bipartite graphs
• Perfectly matchable subgraph problem on a bipartite graph
• Constrained weighted matchings and edge coverings in graphs

Cites work

• Assignment Problems
• Assignment Problems and the Location of Economic Activities
• Assignment problems: a golden anniversary survey
• Balanced optimization problems
• Coloured matchings in bipartite graphs
• Combinatorial optimization. Theory and algorithms.
• Exact perfect matching in complete graphs
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Finding a Minimum Circuit in a Graph
• scientific article; zbMATH DE number 996573 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximum matching of given weight in complete and complete bipartite graphs
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Network flows. Theory, algorithms, and applications.
• On combinatorial optimization and mechanism design problems arising at container ports. With a foreword by Prof. Dr. Erwin Pesch
• On the History of Combinatorial Optimization (Till 1960)
• Planarizing Gadgets for Perfect Matching Do Not Exist
• Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
• Solving the single crane scheduling problem at rail transshipment yards
• Some Matching Problems for Bipartite Graphs
• The complexity of restricted spanning tree problems
• The exact weighted independent set problem in perfect graphs and related classes
• The partitioning min-max weighted matching problem

Cited in

(14)

• Weighted restricted 2-matching
• Minimum perfect bipartite matchings and spanning trees under categorization
• Constrained weighted matchings and edge coverings in graphs
• Facets of an assignment problem with 0-1 constraint
• Solving various weighted matching problems with constraints
• Bottleneck subset-type restricted matching problems
• Low weight perfect matchings
• The partitioning min-max weighted matching problem
• Maximum matching of given weight in complete and complete bipartite graphs
• Balanced problems on graphs with categorization of edges
• Weighted matching as a generic pruning technique applied to optimization constraints
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Some graph optimization problems with weights satisfying linear constraints
• Maximum weight perfect matching problem with additional disjunctive conflict constraints

This page was built for publication: A weighted perfect matching with constraints on weights of its parts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5100129)