-
题名探针区间图和STS-探针区间图的刻划
- 1
-
-
作者
孔静
吴耀琨
-
机构
上海交通大学数学系
-
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
2006年第2期238-244,共7页
-
基金
国家自然科学基金(10301021)
-
文摘
该文首先引入了探针区间序来刻划探针区间图;接着给出STS-探针区间图的探针区间完备的一种构造方法,并借此得到二部图G是相对于给定顶点划分的STS-探针区间图的一个充要条件;同时也说明了STS-探针区间图其实就是其他文献中被独立研究的凸二部图.最后基于前面给出的STS-探针区间图的刻划结果提供了两种简单的O(V+E)时间的STS-探针区间图的判别算法.
-
关键词
区间图
探针区间图
STS-探针区间图
凸二部图
-
Keywords
interval graph
probe interval graph
STS-probe interval graph
convex bipartite graph
-
分类号
O157.5
[理学—数学]
-
-
题名左侧带权凸二分图动态权值匹配
被引量：1
- 2
-
-
作者
祖佺
张苗苗
刘静
-
机构
同济大学软件学院
华东师范大学上海市高可信计算重点实验室
-
出处
《计算机学报》
EI
CSCD
北大核心
2016年第11期2388-2402,共15页
-
基金
国家自然科学基金(61472279,61332008,91318301)资助
-
文摘
动态匹配问题是指在图结构变更的情况下求解某特定匹配,包括添加和删除图中顶点和边的更新操作以及计算匹配信息的查询操作.凸二分图是一类特殊二分图,在其顶点二划分(X,Y)中,Y顶点集为一个全序集,每个x∈X的邻点集在Y中形成一段连续区间.已有的凸二分图动态基数匹配算法不能求解权值匹配,因而该文研究左侧顶点带权凸二分图中动态最大权值匹配问题.文中提出一种问题求解的框架:在更新操作中维护参与匹配的顶点集合,继而在查询操作中计算相应的匹配信息.文中基于交错路定义了可替换集,并证明可通过计算可替换集来维护参与匹配的顶点集;提出紧致子图的概念,证明可替换集的求解等价于紧致子图的求解,从而将传统的通过寻找交替路求解匹配的方法改进为通过寻找子图结构来求解匹配.文中利用凸二分图的凸性质将紧致子图的计算转化为查找该子图中最大或最小y顶点操作,进而结合隐性表征技术在增广平衡二叉查找树数据结构中快速求解,继而设计动态匹配算法在O(log^2|V|)平摊时间下维护更新操作,在最坏线性时间下维护查询操作.较之于已知最好的解决不带权凸二分图动态基数匹配问题的方法,该文提出的方法能在与之相同的时间复杂度下解决难度更高的左侧带权问题.
-
关键词
凸二分图
动态匹配
交错路
紧致子图
隐性表征
平衡二叉查找树
-
Keywords
convex bipartite graph
dynamic matching
alternating path
tight subgraph
implicit representation
balanced binary search tree
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
