How to remove circles from a directed graph?

From	Xu Wang <wangxu.name@Use-Author-Supplied-Address.invalid>
Newsgroups	comp.programming
Subject	How to remove circles from a directed graph?
Date	2011-04-07 15:14 +0200
Message-ID	<201104071314.UTC.inkdc3$mrv$1@tioat.net> (permalink)

Show all headers | View raw

Hello, everyone,

I am trying to solve the following problem, but have not found any solution.

For a directed graph, there are several circles. How to eliminate all 
circles to let the graph become acyclic by removing minimal numbers of arcs?

I tried with set cover problem, hit problem, and so on. However, these 
methods are NP-complete. Is there any linear time complicity method for 
this problem?

Thank you.
Regards,
Xu

Back to comp.programming | Previous | Next — Next in thread | Find similar

Thread

How to remove circles from a directed graph? Xu Wang <wangxu.name@Use-Author-Supplied-Address.invalid> - 2011-04-07 15:14 +0200
  Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 17:35 +0200
    Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 20:26 +0200
    Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 20:42 +0200
  Re: How to remove circles from a directed graph? spinoza1111 <spinoza1111@yahoo.com> - 2011-04-16 07:43 -0700

csiph-web