Re: Algorithm for breaking cycles in directed graph by edge removal

On 1 Sep., 08:19, rdrnws <rdr...@xxxxxxxx> wrote:
[ This is about graph theory, please recommend a more specific newsgroup
if you know one ...]

It is clear to me that a DFS (depth first search) can find all cycles in
a directed graph. DFS will label some edges as "BACK" edges; these back
edges connect a node U to an ancestor node V in the traversal tree.
Obviously, by removing the back edges, all cycles in the graph will be
broken.

However, this solution to the problem is not unique. There may be other
sets of edges - not necessarily containing back edges only - that break
all cycles in the graph when removed from it.

So I am looking for an algorithm that can detect these sets
systematically. I am also looking for a method to determine the minimum
number of edges that have to be removed to break all cycles in the
graph. All pointers to relevant work will be appreciated.

Thanks,

rdr

Maybe try constructing a dynamic programming algorithm to solve the
problem.
.

Relevant Pages

  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Elecsol batteries (again)
    ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
    (uk.rec.waterways)
  • Re: Algorithm for breaking cycles in directed graph by edge removal
    ... It is clear to me that a DFS (depth first search) can find all cycles in a directed graph. ... DFS will label some edges as "BACK" edges; these back edges connect a node U to an ancestor node V in the traversal tree. ...
    (comp.theory)
  • Re: Graph to regions algorithm
    ... > My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... To find cycles in a graph, you compute the "minimum spanning tree". ...
    (comp.graphics.algorithms)
  • Algorithm for breaking cycles in directed graph by edge removal
    ... It is clear to me that a DFS can find all cycles in a directed graph. ... DFS will label some edges as "BACK" edges; these back edges connect a node U to an ancestor node V in the traversal tree. ...
    (comp.theory)
Loading