In varioui practical applications it is convenient to associate a cer I ain graph with a family Z of intervals. One such graph is the well-known overlap graphof Z, whose vertices are the iiitervals in I , with two int...
详细信息
ISBN:
(纸本)081867623X
In varioui practical applications it is convenient to associate a cer I ain graph with a family Z of intervals. One such graph is the well-known overlap graphof Z, whose vertices are the iiitervals in I , with two intervals connected by and edge if imd only if they overlap but neither of them strictly contains the other. The first main contribution of this paper is to propose time- A nd cost-optimal algorithms for computiiig the connected components of an overlap graph. The iask of computing the connected components of an overlap graph arises in numerous applications including traffic control, robot arm manipulation, segmentation of range images, routing, automated surveillance systems, recognizing polygonal configurations, and code generation for parallel niachines. We begin by showing that any sequential algo i ithm that determines the connected components of the overlap graph of a family of n intervals must take Ω(n log n) time in the algebraic tree model. Next, we show that any parallel algorithm for this problem must take Ω(log n) time in the CREW model even if an infinite numbei of processors and meinoiy cells are available. We then go on to show that both the sequential and the parallel lowei bounds are tight by providing matching algorithms running in Θ(n log n) sequential time and Θ(log n) time using n processors in the CREW model, respectively. At the same time, if the endpoints of the intervals are given in sorted ordLi. our sequential algorithm runs in Θ(n)time, improving the best previously known result. It is interesting to note t l i i L t even if the endpoints are sorted, Ω(1og n) is a time lower hound for solving the problem in the CREW model, regaicllrss of the amount of resources available. As an application, we show that our algorithm affords us a time- A nd cost-optimal solution to a restricted version of the single row routing problem. The best previously known result for routing a set of nets without interstreet crossings run5 in O(1og n log l
High-speed electronic sorting networks are difficult to implement with VLSI technology because of the dense and global connectivity required. Optics eliminates this bottleneck by offering global interconnections, mass...
详细信息
High-speed electronic sorting networks are difficult to implement with VLSI technology because of the dense and global connectivity required. Optics eliminates this bottleneck by offering global interconnections, massive parallelism, and noninterfering communications. We present a parallel sorting algorithm and its efficient optical implementation using currently available optical hardware. The algorithm sorts n data elements in a few steps, independent of the number of elements to be sorted. Thus, it is a constant-time sorting algorithm, that is, O(1) time.
The problem considered in this paper is the definition and evaluation of control strategies for handling image features spanning over several partitions of a parallel data structure, whenever such partitions are assig...
详细信息
暂无评论