Dynamic algorithm for graph connectedness?
- From: "Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx>
- Date: Tue, 26 Sep 2006 19:43:19 -0400 (EDT)
Related to the recent thread on minimum vertex covers:
Does anyone here know a good algorithm or data structure for testing
whether a graph has been disconnected by the removal of an edge?
If we're looking for a minimum vertex cover, we're going to be
steadily removing edges from the graph. If the graph becomes
disconnected, then we can run the MVC algorithm independently on
each connected component, and that'll be faster than running a
brute-force MVC algorithm on the whole graph, because 2^x + 2^y
is less than 2^(x+y).
But to do that, we need to be notified when the graph becomes
disconnected. I can't figure out how to do that faster than O(n) ---
remove the edge (a,b), and then try to get from a to b using a
depth-first search. But doing an O(n) algorithm every time an edge
is removed sounds really inefficient!
If the graph is planar, and we already know how to embed it in the
plane, then there's a nice quick (O(lg n)?) algorithm: If we're removing
an edge, and that edge doesn't separate two different faces of the graph,
then we're disconnecting the graph.
What if the graph might not be planar, though?
This seems like a well-studied problem, but I can't find any algorithms
online.
-Arthur
.
- Prev by Date: Re: I was thinking of you King Little Richard. You know I am just looking out for you. <g>
- Next by Date: Re: I was thinking of you King Little Richard. You know I am just looking out for you. <g>
- Previous by thread: Filling a 2x2 array with random numbers such that...
- Next by thread: how to create LocalSystem account
- Index(es):
Relevant Pages
|
