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

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

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

• scientific article; zbMATH DE number 996573 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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 Network Problems
• Faster scaling algorithms for general graph matching problems
• Finding a Minimum Circuit in a Graph
• 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

(13)

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

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)