The minimum cost perfect matching problem with conflict pair constraints

DOI10.1016/J.COR.2012.10.022MaRDI QIDQ340285zbMATH OpenOpenAlexFDO

Authors Temel Öncan, Ruonan Zhang, Abraham P. Punnen

Publication date 14 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2012.10.022

zbMATH Keywords

assignment problemconflict graphconflict pairsmatching problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• Assignment problem with conflicts
• Paths, trees and matchings under disjunctive constraints
• Constrained weighted matchings and edge coverings in graphs
• The minimum spanning tree problem with conflict constraints and its variations

Cited in

(18)

• Approximation of knapsack problems with conflict and forcing graphs
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Solving the set covering problem with conflicts on sets: a new parallel GRASP
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• Minimum cost perfect matching with delays for two sources
• Set covering problem with conflict constraints
• Minimum cost flow problem with conflicts
• A Min-Max Theorem for a Constrained Matching Problem
• Maximum matchings of a digraph based on the largest geometric multiplicity
• Optimal base complexes for quadrilateral meshes
• Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
• Assignment problem with conflicts
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• Minimum cost noncrossing flow problem on layered networks

This page was built for publication: The minimum cost perfect matching problem with conflict pair constraints

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