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 q1SHQlk3018839 for ; Tue, 28 Feb 2012 18:26:47 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApIDANkNTU+GnQCBk2dsb2JhbABCs1IiAQEBAQkJCwkUAySCOBmBGz06h20LmRKgPo0kFAIKAQYLAgYHDBQDAwECAoRDCAEBOgQEQgcygjtjBJU+knI X-IronPort-AV: E=Sophos;i="4.73,497,1325458800"; d="scan'208";a="146487165" Received: from shiva.jussieu.fr ([134.157.0.129]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 28 Feb 2012 18:26:41 +0100 Received: from hydrogene.pps.jussieu.fr (hydrogene.pps.jussieu.fr [134.157.168.1]) by shiva.jussieu.fr (8.14.4/jtpda-5.4) with ESMTP id q1SHQFQ5027375 for ; Tue, 28 Feb 2012 18:26:28 +0100 (CET) X-Ids: 168 Received: from localhost (localhost [127.0.0.1]) by hydrogene.pps.jussieu.fr (Postfix) with ESMTP id 8A174C1091 for ; Tue, 28 Feb 2012 18:26:14 +0100 (CET) Date: Tue, 28 Feb 2012 18:25:41 +0100 From: Pietro Abate To: caml-list@inria.fr Message-ID: <20120228172541.GA20347@zed.irill.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Operating-System: GNU/Linux X-Organization: PPS - =?iso-8859-1?Q?Universit?= =?iso-8859-1?Q?=E9?= Paris Diderot - Paris 7 User-Agent: Mutt/1.5.21 (2010-09-15) X-Miltered: at jchkmail.jussieu.fr with ID 4F4D0E37.001 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)! X-j-chkmail-Enveloppe: 4F4D0E37.001/134.157.168.1/hydrogene.pps.jussieu.fr/hydrogene.pps.jussieu.fr/ Subject: [Caml-list] feedback arc set problem hello world, Before starting coding it myself, I'm wondering if somebody has already a bit of code to solve the minimum feedback arc set problem [1]. Bonus points if your solution considers weighed graphs ... I'm looking for an approximate solution. I've read a few articles and it seems that despite the problem is np-hard, approximate solutions have acceptable bounds . help ? [clearly this is not solved in ocamlgraph, isn't it ?] [1] http://en.wikipedia.org/wiki/Feedback_arc_set