Maximum weight edge-constrained matchings Original Research Article

Practical questions arising from (for instance) biological applications can often be expressed as classical optimization problems with specific, new features. We are interested here in the version of the maximum weight matching problem (on a graph image) obtained by (1) defining a set image of pairs of incompatible edges of image and (2) asking that the matching contains at most one edge in each given pair. Such a matching is called an odd matching. The graph image, where image is the set of edges of image occurring in at least one pair of image, is called the trace-graph of image and image.