0
0

[–] SelfReferenceParadox ago 

Just off the top of my head, it sounds to me like this may reduce to the Travelling Salesman Problem, making this a very difficult problem to solve for large data sets, like you wanted. If you're OK with getting a non-optimal answer, some kind of heuristic.

0
0

[–] CaptainParanoia ago 

Not quite, TSP visits all nodes. And there is software like CONCORDE that can handle very large instances.

0
2

[–] CaptainParanoia 0 points 2 points (+2|-0) ago  (edited ago)

You can model it as a directed graph, your edges are compatible donations (donor -> patient) and family relations (patient -> family member). People who donate and don't want anything in return have incoming edges from all patients.

Then you can pick a patient A and use Dijkstra's algorithm to find the shortest path A -> A. That should give you a chain of trades.

0
0

[–] randrews ago 

D only donates the kidney if B agrees to donate his though, right? Because otherwise it's really simple and C is left screwed.