Extreme Vertex Sets
Hiroshi Nagamochi, Toshihide Ibaraki · Cambridge University Press eBooks · 2008
The concept of extreme vertex sets, defined in Section 1.5.3, was first introduced by Watanabe and Nakamura [308] to solve the edge-connectivity augmentation problem. The fastest deterministic algorithm currently known for computing all extreme vertex sets was given by Naor, Gusfield, and Martel [259]. Their algorithm first computes the Gomory–Hu cut tree of the graph and then finds all maximal k -edge-connected components for some k , from which all extreme vertex sets are identified by Lemma 1.42, taking O ( n ( mn log( n 2 /m )) running time. Bencz&úr and Karger [20] have given a Monte Carlo–type randomized algorithm, which runs in O ( n 2 log 5 n ) time but is rather involved. Notice that computing all extreme vertex sets is not easier than finding a minimum cut since at least one of the extreme vertex sets is a minimum cut. In this chapter, we give a simple and efficient algorithm for computing all extreme vertex sets in a given graph, and we show some applications of extreme vertex sets. The algorithm will be used to solve the edge-connectivity augmentation problem in Section 8.3. In Section 6.1,we design a deterministic O ( nm + n 2 log n ) time algorithm for computing the family χ( G ) of extreme vertex sets in a given edge-weighted graph G , which is a laminar family, as observed in Lemma 1.41. As a new application of extreme vertex sets, in Section 6.2 we consider a dynamic graph G in which the weight of edges incident to a designated vertex may increase or decrease with time and we give a dynamic minimum cut algorithm that reports a minimum cut of the current G whenever the weight of an edge is updated.