How to solve this Graphical problem?

Revision en4, by Inversentropir-36, 2020-11-19 07:25:35

Give you an undirected graph with no guarantee of connectivity, Erase 2 edges to minimize the maximum connected block. You only need to output The size of the largest connected block.

How to solve it in less than O(N^2) Time Complexity ?

Sorry of my suck English :(

UPD: We have found an another O(N^2) Algorithm. We can check all edges, try to delete the edges that we are checking, and then use the Tarjan's algorithm (Tarjan, R. E. (1974). "A note on finding the bridges of a graph") for the remaining edges. Perhaps optimizing this algorithm can reduces time complexity.

Tags #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Inversentropir-36 2020-11-19 07:25:35 69
en3 English Inversentropir-36 2020-11-18 11:08:32 247 UPdate for our new algorithm.
en2 English Inversentropir-36 2020-11-16 08:56:02 2 Tiny change: 'cted block。\n\nHow to' -> 'cted block.\n\nHow to'
en1 English Inversentropir-36 2020-11-16 08:53:14 307 Initial revision (published)