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 p6TFoTEh026123 for ; Fri, 29 Jul 2011 17:50:29 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArUAAIvVMk7RVdW+kGdsb2JhbAA0AQEBAQMBAQERAlIdEQwYOhQPBRIBBQEkRZdtRI8MCBQBAQEBCQkNBxQEIYkAohEKjCuHFzuIcoZBBIdag26TfTyDfA X-IronPort-AV: E=Sophos;i="4.67,287,1309730400"; d="scan'208";a="114458286" Received: from mail-yx0-f190.google.com ([209.85.213.190]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 29 Jul 2011 17:50:22 +0200 Received: by yxk8 with SMTP id 8so4353889yxk.27 for ; Fri, 29 Jul 2011 08:50:21 -0700 (PDT) Received: by 10.91.96.4 with SMTP id y4mr263623agl.53.1311954621648; Fri, 29 Jul 2011 08:50:21 -0700 (PDT) Path: glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: fa.caml Date: Fri, 29 Jul 2011 08:50:21 -0700 (PDT) In-Reply-To: Reply-To: fa.caml@googlegroups.com Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=138.37.88.134; posting-account=e5mzsQoAAAB7g9y7Bkgam0zJDHRr7bCB NNTP-Posting-Host: 138.37.88.134 References: User-Agent: G2/1.0 X-Google-Web-Client: true MIME-Version: 1.0 Message-ID: <5491ca2c-2f03-4c6f-a915-edc7ef6f79a0@glegroupsg2000goo.googlegroups.com> From: Radu Grigore To: fa.caml@googlegroups.com Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Poset variant of union-find datastructure On Wednesday, July 27, 2011 9:22:16 PM UTC+1, Guillaume Yziquel wrote: > 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. What you want is known as "dynamic transitive closure" or, more precisely, "incremental transitive closure." See, for example, http://scholar.google.co.uk/scholar?cluster=2214623839872244490 as a starting point.