Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38319
標題: Parallel Algorithms on Circular-Arc Graphs
作者: M.G.
rews
D.T.Lee
Project: Computational Geometry: Theory and Applications, Volume�5, Issue�3, Page(s) �117-141.
摘要: 
Given a set of n circular arcs, the problem of finding a minimum cut has been considered in the sequential model. Here we present a parallel algorithm in the EREW-PRAM model that runs in O(log n) time with O(n) processors if the arcs are not given already sorted and using View the MathML source processors otherwise. On the hypercube model, we consider the minimum cut as well as the following problems on a set of n circular-arcs: the minimum dominating set, the minimum circle cover, the maximum independent set, and the minimum clique cover. We give a parallel algorithm of time complexity O(log n log log n) and processor complexity O(n) for the minimum dominating set problem based on the hypercube model. For the minimum cut sequence, minimum circle cover, minimum clique cover, and maximum independent set problems, we give parallel algorithms of time complexity O(log n log log n + log m) and processor complexity O(n) if the input is not given sorted, otherwise, the time complexity is O(log n log m); m is the size of the solution set.
URI: http://hdl.handle.net/11455/38319
DOI: 10.1016/0925-7721(94)00024-P
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.