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

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

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

(22)

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

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)