Dynamic weight matchings in left weighted convex bipartite graphs

The dynamic matching problem is the problem of maintaining certain matchings in dynamically changing graphs under a set of update operations that includes inserting and deleting vertices and edges, and a set of query operations that includes obtaining the matching status of a vertex or finding the mate of a matched vertex. Convex bipartite graph is a bipartite graph with the vertex bipartition (X,Y) in which the neighborhood of each x∈X forms an interval of Y where Y is linearly ordered. The existing algorithm for dynamic cardinality matching in convex bipartite graphs cannot solve dynamic maximum weighted matching. And this paper researches dynamic maximum weight matching in left weighted convex bipartite graphs. To solve this problem, we propose a framework that is maintaining the set of vertices participating in the matching in the update operations, and based on the set, computing the matching information in the query operations. We define the concept of replaceable set, i.e., the set of matched vertices reachable by alternating paths from an unmatched vertex, and prove that the computation for replaceable sets is sufficient to maintain the matched vertex set. We then define the concept of tight subgraph, and prove that computing a replaceable set is equivalent to finding a certain tight subgraph. Thus, the traditional way of computing matchings via finding alternating paths is reduced to our approach of computing matchings via finding a subgraph structure. Utilizing the convexity property of a convex bipartite graph, we further put forward a method to find a tight subgraph by searching for the maximum or minimum y vertices in the subgraph. The method can be efficiently implemented in an augmented balanced binary search tree data structure with the implicit representation of the subgraph. Then we design algorithms that maintain the update operations in O(log²|V|) amortized time and the query operations in worst-case linear time, which achieves the same time bound as the best known solution to the dynamic cardinality matching problem in the unweighted situation.