Graph Algorithm for Dismantling
A graph has n vertices and m edges. The graph begins connected and then edges are removed in the order that they appear in the list. At the end of the process, the graph is disconnected.
Therefore, there is a specific edge in the list of edges such that before removing it, there is one connected component with more than the floor of n/4 vertices. After removing this edge, there is no connected component in the graph with more than the floor of n/4 vertices.
How I would go about devising the best algorithm to find this edge. Do I just begin removing edges and then traverse the graph each time to check to see if the largest connected component suffices? That runs in O(nm) time but I feel like there must be some faster way. I think the answer has something to do with using disjointed sets to find the connected components but I'm not certain on how to go about implementing that.
Consider running this process in reverse, adding in edges rather than deleting edges. That process bears a strong resemblance to Kruskal's algorithm (every node starts off by itself and edges are added in that link up different connected components), except that you stop as soon as there's at least one connected component with at least ⌊n/4⌋ nodes in it.
One way to solve this would then be to use a modified version of Kruskal's algorithm and a union-find data structure augmented so that each representative in the union-find structure stores the number of nodes in its connected component. Traverse the edges in reverse order, at each point discarding the edge if the endpoints are already connected and otherwise linking them. If you add in an edge that causes there to be a connected component of at least ⌊n/4⌋ nodes, you've found the edge that you're looking for. This will run in time O(n + mα(n)) if you use a fast implementation of the union-find data structure, which is essentially linear in practice.
链接地址: http://www.djcxy.com/p/70670.html下一篇: 图解算法