All-cavity maximum matchings
Let \(G=(X,Y,E)\) be a bipartite graph with integer weights on the edges. Let \(n,m\), and \(N\) denote the number of vertices, the number of edges, and an upper bound on the absolute values of edge weights of \(G\), respectively. For a vertex \(u\) in \(G\), let \(G_u\) denote the subgraph constructed by deleting \(u\) from \(G\). The all-cavity maximum matching problem asks for a maximum weight matching in \(G_u\) for all \(u\) in \(G\). In this paper, the authors show that the problem is solvable in \(O(\sqrt nm\log (nN))\) time, matching the currently best time complexity for merely computing a single maximum weight matching in \(G\) given by \textit{H. N. Gabow} and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 38, No. 4, 815-853 (1991; Zbl 0799.68145)]. The authors also give a \(O(n^2 \log n+nm)\) running time algorithm for a generalization of the problem where both a vertex from \(X\) and one from \(Y\) can be deleted. For the entire collection see [Zbl 0879.00060].
This page was built for publication: All-cavity maximum matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370211)
