For an undirected connected graph, how create an index of the bridges maintained after removal of edges?

user_1687259 0
Viewed 171

Creating an index itself is the same as computing the list of bridges. The question is about how to maintain that index after removing an edge without recomputing it altogether.

Maybe storing the list of all (simple) cycles and removing all cycles that required that edge (index maintenance) would work together with "is this edge in a cycle" to check its requiredness. For a bigger graph, this would be quite expensive to compute initially because the number of cycles grows exponentially with the degree of connectedness.

EDIT: an algorithm that would give a probabilistic answer might also work

P.S. Here's an excerpt from "Introduction to Algorithms" for the terminology terminology excerpt picture

edges connected-components undirected-graph graph indexing
1 Answers

One way to reduce amount of work when recomputing the list of the bridges after an edge removal would be to build a list of no-bridge components along with the list of bridges (where no-bridge components means a maximal connected subgraph without any bridge - in the picture bcc components "2+3" would form one such no-bridge component - since they don't have any bridge, only one articulation point). Bridges in the graph will always connect 2 such no-bridge components. Also if you merge all points of each no-bridge component into one point you'll end up with a graph which only has one edge per bridge of original graph and guaranteed no cycles (otherwise the bridge could be removed and graph would stay connected). So e.g. for the graph on the picture you can look at it as the following:

 Component1 - Components 2+3 - Component 4 - Component 6
                    |                         /        \     
               One-point                Component 5    One-point

Now with such representation the algorithm for updating list of bridges will need to look at the edge being deleted and act as following:

  1. If edge deleted is one of bridges - graph is no longer connected.
  2. Otherwise the edge being deleted belongs to one of bi-connected each edge which was the bridge still will be the bridge + there might be new bridges appearing. It will be guaranteed that new bridge might only appear in the component to which deleted edge belongs - so we can rebuild the list of bridges only for that subgraph and if there are bridges there split the graph into no-bridge components

In the example on the picture - e.g. edge from component 4 was deleted. In that case we would only need to look at the component 4 itself, determine that now all 3 left edges are bridges and add them to the set of bridges + no-bridge component 4 with three "one-point" components (though one-point components are not really needed for this purpose since they don't contain any edges).

In this case we always have to rebuild the list of bridges only for the no-bridge component that the edge is being deleted from. Unfortunately if your original graph had no bridges (i.e. it was one large no-bridge component) this doesn't really help you much, though you could argue that starting point "there are no bridges" doesn't contain a lot of information too.

I don't claim this is the best you can do, but it does answer your question "maintain that index after removing an edge without recomputing it altogether" to the degree that you only need to check one no-bridge component after each edge removal.

For the algorithm of building a list of bridges from scratch (in the beginning on the process or when you need to apply it to one no-bridge component) you can e.g. use an algorithm described here which works in O(V+E) time.

user_118396860
Related