Le Thursday 28 Jul 2011 à 10:53:37 (+0200), Christophe Raffalli a écrit :
> Le 27/07/2011 22:20, Guillaume Yziquel a écrit :
> > Hi.
> >
> > I'm wondering if people on this list may have any insight as to how
> > implement a "poset-find" datastructure much like a union-find
> > datastructure.
> >
> > A typical union find signature can be found here:
> >
> > http://www.enseignement.polytechnique.fr/informatique/INF564/html/unionFind.mli.html
>
> Hello,
>
> I only see the graph solution (unfortunately) ... With variants:
>
> I would be very happy too if there were a more efficient solution
> (logarithmic complexity both for relation and relate ?)
The most relevant paper I could find on the topic is the following:
http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf
> Cheers,
> Christophe
Best regards,
--
Guillaume Yziquel
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
