Faster dynamic matchings and vertex connectivity
Piotr Sankowski · Symposium on Discrete Algorithms · 2007
We present first fully dynamic subquadratic algorithms for: computing maximum matching size, computing maximum bipartite matching weight, computing maximum number of vertex disjoint s, t paths and testing directed vertex k-connectivity of the graph. The presented algorithms are randomized. The algorithms for maximum matching size and disjoint paths support operations in O(n1.495) time. The algorithm for computing the maximum bipartite matching weight maintains the graph with integer edge weights from the set 1,..., W in O(W2.495n1.495) time. The algorithm for testing directed vertex k-connectivity supports updates in O(n1.575 + nk2) time. For all of these problems the presented dynamic algorithms break the input size barrier --- O(n2).As a side result we obtain a dynamic algorithm for the dynamic maintenance of the rank of the matrix that support updates in O(n1.495) time.