Re: Computing cut nodes and bridges in directed graphs

Please let me be more precise about the algorithm we already have. We are interested in computing the vector CN, where CN(i)=CutNodes(g,source,i) (i.e., the set of vertexes appearing in all paths from source to i in the directed graph g). The algorithm that we already have is the following:

T0:=DFS(g,source)
for i \in vertexes(g) do
   CN(i):= if i \in vertexes(T0) then \emptyset else vertexes(g) end
end
for i \in vertexes(T0) do
   T1:=DFS(RemoveVertex(T0,i),source)
   for j \in vertexes(T0)-vertexes(T1) do
      CN(j):=CN(j) \cup {i}
   end
end

Assume that DFS returns the reachability tree. CN(i) is initialized with \emptyset or vertexes(g) depending on whether i is reached from the source (the point is that, under our definition, any vertex is a cut node between the source and i if i is not reached from the source). Then, we simply try each potential cut node and update the corresponding sets. So our computation of cut nodes is O(V*(V+E)).

Actually, our computation of bridges is O(V*(V+E)) too since we only consider the edges in the reachability tree (whose cardinality is proportional to |V|). Indeed, we take advantage of the fact that e \in Bridges(g,source,i) implies that e \in edges(DFS(g,souce)):

T0:=DFS(g,source)
for e \in edges(g) do
   BE(e):= if e \in edges(T0) then \emptyset else edges(g) end
end
for e1 \in edges(T0) do
   T1:=DFS(RemoveEdge(T0,e1),source)
   for e2 \in edges(T0)-edges(T1) do
      BE(e2):=BE(e2) \cup {e1}
   end
end

Give each edge unit weight and label it with an i->j max flow.  If I am
reading your definition correctly all cutnodes will have an inflow
(outflow) equal to the outflow of i (inflow of j).  All bridges will
themselves carry the same magnitude of flow.


I see your point! However, I still have problems with the complexity you are suggesting.

I only realized after I wrote that you could use Ford Fulkerson, which
in this special case will run in O(|E|d) where d is the maximum of
indegree and outdegree of all nodes of the graph.

If understand correctly, you suggest that for each CN(i) we invoke Ford Fulkerson's algorithm. So computing CN would be O(V*E*d), which is higher than O(V*(V+E))

Luis
.

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Why does Cantor a target for cranks?
    ... and wildberger doesn't give this the recognition it deserves ... that if we have a computing process that generates a stream of ... then it's meaningful for such a specific process (algorithm) ... or conflating various groups of order 6 into the ...
    (sci.math)
  • Re: Correctness proving (Was: Clear and Unambiguous SOFTWARE requirements/specifications possible?)
    ... We come up with reasonable schemes that find "good" results (by some ... The bulk of OR techniques -- like linear programming, dynamic programming, Out Of Kilter, etc. -- all provide a deterministic solution for problems like Traveling Salesman that will always be the absolute optimum. ... Solving np-Complete problems requires both an algorithm and a representation of the problem that is appropriate for the algorithm. ... The issue here is proving correctness of programs that are well-formed within the constraints of the computing space. ...
    (comp.software.testing)
  • Re: Penroses Computing Pi Description?
    ... > <snip penrose> ... > digit as output. ... > "computing Pi" on its own, ... is the algorithm the computation of one particular digit or is ...
    (sci.logic)
  • Re: qubits
    ... One cycle of the algorithm would collapse ... Most np-Complete problems have been ... Thus any Qubit ... Though Qubits has obvious potential for increasing computing power at ...
    (comp.object)