  We consider a well-studied online random graph model for kidney exchange,
where nodes representing patient-donor pairs arrive over time, and the
probability of a directed edge is p. We assume existence of a single altruistic
donor, who serves as a start node in this graph for a directed path of
donations. The algorithmic problem is to select which donations to perform, and
when, to minimize the amount of time that patients must wait before receiving a
kidney.
  We advance our understanding of this setting by (1) providing efficient (in
fact, linear-time) algorithms with optimal O(1/p) expected waiting time, (2)
showing that some of these algorithms in fact provide guarantees to all
patients of O(1/p) waiting time {\em with high probability}, (3) simplifying
previous analysis of this problem, and (4) extending results to the case of
multiple altruistic donors.
