paralell assignment problem
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050209 (13:53) 
From:  skaller <skaller@u...> 
Subject:  Re: [Camllist] Re: paralell assignment problem 
On Wed, 20050209 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 NPcomplete: > 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 OCamlrelated 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 reccall 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 nonoptimal 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: 061296600850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net