user1806566
user1806566

Reputation: 1251

Is there an efficient way to find nested biconnected components in a biconnected graph

I have a biconnected graph (i.e., an undirected graph where removing any single vertex leaves the graph connected). I would like to find the "nested bidirected subgraphs," meaning that the subgraph is biconnected when examined by itself, and it's connected to the rest of the graph through a single vertex on either end. Is there an efficient algorithm for finding these?

I know that we can find all bidirected components of a graph in O(V+E) time using Tarjan's algorithm. That's not directly applicable, though, because the entire graph is one large biconnected component. I was thinking that if I removed each edge from the graph one-by-one and searched for bidirected components, I could find what I'm looking for (and then have to apply the process recursively on the components I've found), but that seems very brute-force. Is there a better way?

Upvotes: 2

Views: 63

Answers (0)

Related Questions