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

rdrnws 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.

Is your problem effectively "maximum spanning tree"? If so, that may be
a useful search term.

Patricia
.

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
    ... DFS will label some edges as "BACK" edges; ... Obviously, by removing the back edges, all cycles in the graph will be ... Maybe try constructing a dynamic programming algorithm to solve the ...
    (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