請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38263
標題: Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems
作者: M.G.
rews
M.J.Atallah
D.Z.Chen
D.T.Lee
關鍵字: Parallel algorithms, maximum matching problems, interval graphs, complement graphs, EREW PRAM, hypercubes.
出版社: Springer-Verlag
摘要: Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log 3 n) time using O(n/ log 2 n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs.
URI: http://hdl.handle.net/11455/38263
ISSN: 0178-4617
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。