Re: [Caml-list] Re: paralell assignment problem

[skaller <skaller@users.sourceforge.net>]

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