1
$\begingroup$

Questions:

  • who first posed the problem of determining a collection of (directed) cycles, whose edgeweight sum is minimal and, for which each vertex belongs to exactly one of the cycles?

  • who came up with the solution of duplicating the vertex set and thus reducing the problem to a minimum-weight bipartite matching?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I just found an online publication related to the problem: "The Cycle Cover Problem" by J.L. Szwarcfiter and B.L. Wilson, Technical Report No 131 1979, University of Newcastle upon Tyne, UK.

As that report's investigation of the cycle cover problem is inspired by Karp's list of 21 NP-complete problems, I would be surprised if an earlier reference could be found.

Edit:
in that report is also a (the first?) definition of 3-dimensional matching.

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .