Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
paralell assignment problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-09 (13:53)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Re: paralell assignment problem
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:

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,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language