左侧带权凸二分图动态权值匹配

Dynamic Weight Matchings in Left Weighted Convex Bipartite Graphs

动态匹配问题是指在图结构变更的情况下求解某特定匹配,包括添加和删除图中顶点和边的更新操作以及计算匹配信息的查询操作.凸二分图是一类特殊二分图,在其顶点二划分(X,Y)中,Y顶点集为一个全序集,每个x∈X的邻点集在Y中形成一段连续区间.已有的凸二分图动态基数匹配算法不能求解权值匹配,因而该文研究左侧顶点带权凸二分图中动态最大权值匹配问题.文中提出一种问题求解的框架:在更新操作中维护参与匹配的顶点集合,继而在查询操作中计算相应的匹配信息.文中基于交错路定义了可替换集,并证明可通过计算可替换集来维护参与匹配的顶点集;提出紧致子图的概念,证明可替换集的求解等价于紧致子图的求解,从而将传统的通过寻找交替路求解匹配的方法改进为通过寻找子图结构来求解匹配.文中利用凸二分图的凸性质将紧致子图的计算转化为查找该子图中最大或最小y顶点操作,进而结合隐性表征技术在增广平衡二叉查找树数据结构中快速求解,继而设计动态匹配算法在O(log^2|V|)平摊时间下维护更新操作,在最坏线性时间下维护查询操作.较之于已知最好的解决不带权凸二分图动态基数匹配问题的方法,该文提出的方法能在与之相同的时间复杂度下解决难度更高的左侧带权问题.

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∈Xforms an interval of Y where Yis 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 tightsubgraph,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 minimumyvertices 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^2|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.