From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id EDB44BC88 for ; Wed, 9 Feb 2005 14:53:44 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j19DriLt002430 for ; Wed, 9 Feb 2005 14:53:44 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA03187 for ; Wed, 9 Feb 2005 14:53:44 +0100 (MET) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j19DrfOn002421 for ; Wed, 9 Feb 2005 14:53:42 +0100 Received: from [192.168.1.200] (ppp212-197.lns2.syd3.internode.on.net [203.122.212.197]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j19DrPjQ009407; Thu, 10 Feb 2005 00:23:36 +1030 (CST) Subject: Re: [Caml-list] Re: paralell assignment problem From: skaller Reply-To: skaller@users.sourceforge.net To: Pascal Zimmer Cc: Radu Grigore , caml-list In-Reply-To: <4209F53D.5030506@sophia.inria.fr> References: <1107832025.13571.260.camel@pelican.wigram> <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> <1107882489.5022.175.camel@pelican.wigram> <7f8e92aa05020810335ab052e0@mail.gmail.com> <7f8e92aa050209014322b561e@mail.gmail.com> <4209F53D.5030506@sophia.inria.fr> Content-Type: text/plain Message-Id: <1107957205.5022.610.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 10 Feb 2005 00:53:25 +1100 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 420A15E8.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 420A15E5.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 wrote:01 subset:01 convincing:01 ocaml:01 ocaml:01 ackermann:01 stack:01 recursive:01 glebe:01 nada:98 ...:98 ...:98 061:98 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: On Wed, 2005-02-09 at 22:34, Pascal Zimmer wrote: > The problem can now be rephrased as: "Given a directed graph, find a > minimal set of vertices whose deletion leaves an acyclic graph". To put > it another way, "given a directed graph G=(V,E), find a minimal subset > of vertices V' such that every cycle of G has a vertex in V'". > This problem is known as the minimum feedback vertex set, and (sadly) it > is NP-complete: > http://www.nada.kth.se/~viggo/wwwcompendium/node19.html#3336 Ah, thanks, it reduces to a known problem. > Last, to comment Skaller's last post: [] > Actually, they are fully equivalent. Your argument is fully convincing, thanks (I'm relieved, since I've already implemented the algorithm :) > Hope this helps... Indeed, thanks to everyone who contributed! > PS: I am not sure this conversation is much OCaml-related anymore... It probably wasn't in the first place, but this list has a lot of friendly people with theoretical knowledge and analytical skills: seemed like a good place to ask. However, the algorithm could be applied in Ocaml in the circumstances which lead me to the problem, namely tail rec-call optimisation. Is Ocaml doing this already? >>From the ackermann tests I did it looks like stack frame size is dominant in heavily recursive routines, and the extra variables introduced by a non-optimal tail call are only temporaries, so perhaps it isn't worthwhile, as Marcin suggested, but then I don't know anything about how Ocaml works.. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net