The Python garbage collection algorithm adds a separate cycle collection phase in addition to reference counting. Periodically the garbage collector does a pass over the objects that subtracts references from tracked objects; the objects left with non-zero refcounts have external roots and a regularly mark-and-sweep phase proceeds from there. I believe the basic algorithm was introduced by Lins, but I can't recall the reference.
Eich's post reminded me of an alternate scheme by David Bacon and others. See the April 2005 paper by Paz et al. The key idea is that garbage cycles are only created when an object has its reference count decremented to a value greater than zero. If you have a cycle, it only becomes collectible when the last reference outside the cycle goes away; thus, a decref is necessary to collect the cycle. The key idea is to limit the garbage collection to a set of candidate objects that have recently been decrefed. It seems like a fairly straightfoward addition to Python.