Dynamic matchings in left vertex weighted convex bipartite graphs

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph $$G=(X,Y,E)$$ G = ( X , Y , E ) in which the neighbors of each $$x\in X$$ x ∈ X form an interval in $$Y$$ Y where $$Y$$ Y is linearly ordered, and each $$x\in X$$ x ∈ X has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in $$O(\log ^2{|V|})$$ O ( log 2 | V | ) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case $$O(k)$$ O ( k ) time, where $$k$$ k is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.