Browsing Technical and Research Reports by Author "Ritt, Marcus Rolf Peter"
Now showing items 1-1 of 1
-
Maximum matching with ordering constraints is NP-complete
Ritt, Marcus Rolf Peter (2009) [Technical and Research Report]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 ...