A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints

DOI10.1016/j.endm.2018.01.002zbMath1388.90123OpenAlexW2790483745MaRDI QIDQ1742190

Temel Öncan, Ị. Kuban Altınel

Publication date: 11 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2018.01.002

zbMATH Keywords

branch and boundassignment problemconflict graphbipartite perfect matching problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (3)

Minimum cost flow problem with conflicts ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Assignment problem with conflicts

Cites Work

• Unnamed Item
• The minimum cost perfect matching problem with conflict pair constraints
• The maximum flow problem with disjunctive constraints
• Polynomially solvable special cases of the quadratic bottleneck assignment problem
• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• The NP-completeness of the bandwidth minimization problem
• The quadratic assignment problem. Theory and algorithms
• The Knapsack Problem with Conflict Graphs
• Assignment Problems
• Handbook of metaheuristics

This page was built for publication: A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints