From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6SH4VlI013320 for ; Thu, 28 Jul 2011 19:04:31 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnoCAGiVMU5V2gB4hWdsb2JhbAA0AQEDAQF+BwUMDFIUAS0qJBOnVQEBAQoLCwUWJYh8AgLCRw6GMwSjXw X-IronPort-AV: E=Sophos;i="4.67,283,1309730400"; d="scan'208";a="114352378" Received: from emailfrontal1.citycable.ch ([85.218.0.120]) by mail1-smtp-roc.national.inria.fr with SMTP; 28 Jul 2011 19:04:26 +0200 X-Alinto-smtpauth-localdomain: Yes Received: from seldon (unknown [85.218.93.111]) (Authenticated sender: guillaume.yziquel@citycable.ch) by emailfrontal1.citycable.ch (Postfix) with ESMTPA id 8C2ECE64343; Thu, 28 Jul 2011 19:04:11 +0200 (CEST) Received: from yziquel by seldon with local (Exim 4.72) (envelope-from ) id 1QmTzV-0001uV-Hx; Thu, 28 Jul 2011 19:03:21 +0200 Date: Thu, 28 Jul 2011 19:03:21 +0200 From: Guillaume Yziquel To: Christophe Raffalli Cc: caml-list@inria.fr Message-ID: <20110728170321.GY21817@localhost> References: <20110727202007.GG21817@localhost> <4E312391.9030703@univ-savoie.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline In-Reply-To: <4E312391.9030703@univ-savoie.fr> User-Agent: Mutt/1.5.20 (2009-06-14) Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p6SH4VlI013320 Subject: Re: [Caml-list] Poset variant of union-find datastructure 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