左侧带权凸二分图动态权值匹配
动态匹配问题是指在图结构变更的情况下求解某特定匹配，包括添加和删除图中顶点和边的更新操作以及计算匹配信息的查询操作。凸二分图是一类特殊二分图，在其顶点二划分（X ，Y ）中，Y 顶点集为一个全序集，每个x∈X 的邻点集在Y 中形成一段连续区间。已有的凸二分图动态基数匹配算法不能求解权值匹配，因而该文研究左侧顶点带权凸二分图中动态最大权值匹配问题。文中提出一种问题求解的框架：在更新操作中维护参与匹配的顶点集合，继而在查询操作中计算相应的匹配信息。文中基于交错路定义了可替换集，并证明可通过计算可替换集来维护参与匹配的顶点集；提出紧致子图的概念，证明可替换集的求解等价于紧致子图的求解，从而将传统的通过寻找交替路求解匹配的方法改进为通过寻找子图结构来求解匹配。文中利用凸二分图的凸性质将紧致子图的计算转化为查找该子图中最大或最小 y 顶点操作，进而结合隐性表征技术在增广平衡二叉查找树数据结构中快速求解，继而设计动态匹配算法在 O（log2｜V｜）平摊时间下维护更新操作，在最坏线性时间下维护查询操作。较之于已知最好的解决不带权凸二分图动态基数匹配问题的方法，该文提出的方法能在与之相同的时间复杂度下解决难度更高的左侧带权问题。
凸二分图、动态匹配、交错路、紧致子图、隐性表征、平衡二叉查找树
39
TP301(计算技术、计算机技术)
国家自然科学基金61472279，61332008，91318301资助．
2016-11-30（万方平台首次上网日期，不代表论文的发表时间）
共16页
2388-2403
