未找到相关数据
An NC1 algorithm for the persistency problem in bipartite graphs
被引：0
作者：
Lakhal, J
Litzler, L
机构：
来源：
PARALLEL AND DISTRIBUTED COMPUTING SYSTEMS - PROCEEDINGS OF THE ISCA 9TH INTERNATIONAL CONFERENCE, VOLS I AND II
|
1996年
关键词：
persistency;
matching;
transitive closure;
parallel algorithm;
combinatorial optimization;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Let G = [U, V, E] be a bipartite graph and lee n = \ U \ + \ V \ and m = \ E \. The persistency problem in bipartite graphs consists in making the following 3-partition of E: the set of edges belonging to all maximum matchings, the set of edges belonging to no maximum matching and the set of edges belonging to at least one maximum matching but not to all of them. We propose a sequential and a parallel algorithm for the persistency problem. The first one improves the known sequential bound of this problem when the graph is dense. If a maximum matching is known, the parallel algorithm takes O(log n) time using O(n(3)) processors.
引用
收藏
页码：450 / 455
页数：6
相关论文