Maximum matching with ordering constraints is NP-complete
Marcus Ritt · Americanae (AECID Library) · 2009
A maximum weighted matching in a graph can be computed in polynomial time. In this paper we show that a variant, where the matching lias to respect additional ordering constraints between the vertices makes the problem NP-complete.