Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada <luque@xxxxxxxxxxxxxx>
- Date: Mon, 08 Aug 2005 10:49:57 +0200
Dear Gene:
Could you elaborate more on this please? How can I use Dinic's algorithm for computing the *sets* of cut nodes and the *sets* of bridges?Look at max flow algorithms like Dinic's. If memory serves it's O(|V|^2 |E|), and you might be able to do incremental updates more cheaply.
Why the complexity you are suggesting is better than the one I already have?
Notice that I compute *all* the sets CutNodes(g,source,i) (for every vertex i in V) in O(V*(V+E)). It is true that the computation of all the sets Bridges(g,source,e) (for every edge e in E) takes O(E*(V+E)), but I don't see how you can compute this information using Dinic's algorithm. Could you explain, please?
Luis .
- Follow-Ups:
- References:
- Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Gene
- Computing cut nodes and bridges in directed graphs
- Prev by Date: Re: Computing cut nodes and bridges in directed graphs
- Next by Date: Re: Computing cut nodes and bridges in directed graphs
- Previous by thread: Re: Computing cut nodes and bridges in directed graphs
- Next by thread: Re: Computing cut nodes and bridges in directed graphs
- Index(es):
Relevant Pages
|
