Despite the unfortunately similar title, this paper solves a significantly more general problem than the "Minimizing Digraphs" paper from 2006. The 2006 paper minimized graphs with labelled edges, as in the offline algorithm of Cardon and Crochemore, and the new paper minimizes graphs with indistinguishable potentially-duplicate edges, as in the offline "relational coarsest partition" algorithm of Paige and Tarjan.
PostScript compressed with bzip2
I submitted a paper "Hash-Consing of Regular Trees in O(n log n)" to Algorithmica on 2004-11-24. Unfortunately, it contained a serious error: Theorem 2 is completely wrong, as was pointed out a few days later by Laurent Mauborgne:
Counter-example for theorem 2 :
a0->a1->a2->...->an where the cycle is minimal and the new component to
^--a0------/ be added is a0.
I dislike leaving links completely broken, and
there might even still be some value in the rest of the paper. In particular, the
Theorem 1 trick still tends to improve the performance over earlier algorithms.
Therefore the draft is
still available here.
However, without Theorem 2 the worst case behavior of the algorithm is no better
than earlier algorithms, so publication is off unless some replacement for
Theorem 2 can be found.