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...
详细信息
Welcome to the proceedings of GCC2004 and the city of Wuhan. Grid computing has become a mainstream research area in computer science and the GCC conference has become one of the premier forums for presentation of new...
详细信息
ISBN:
(数字)9783540302070
ISBN:
(纸本)9783540235781
Welcome to the proceedings of GCC2004 and the city of Wuhan. Grid computing has become a mainstream research area in computer science and the GCC conference has become one of the premier forums for presentation of new and exciting research in all aspectsofgridandcooperativecomputing. Theprogramcommitteeispleasedtopresent the proceedings of the 3rd International Conference on Grid and Cooperative Comp- ing (GCC2004), which comprises a collection of excellent technical papers, posters, workshops, and keynote speeches. The papers accepted cover a wide range of exciting topics, including resource grid and service grid, information grid and knowledge grid, grid monitoring,managementand organizationtools, grid portal, grid service, Web s- vices and their QoS, service orchestration, grid middleware and toolkits, software glue technologies, grid security, innovative grid applications, advanced resource reservation andscheduling,performanceevaluationandmodeling,computer-supportedcooperative work, P2P computing, automatic computing, and meta-information management. The conference continues to grow and this year a record total of 581 manuscripts (including workshop submissions) were submitted for consideration. Expecting this growth, the size of the program committee was increased from 50 members for GCC 2003 for 70 in GCC 2004. Relevant differences from previous editions of the conf- ence: it is worth mentioning a signi?cant increase in the number of papers submitted by authors from outside China; and the acceptance rate was much lower than for p- vious GCC conferences. From the 427 papers submitted to the main conference, the program committee selected only 96 regular papers for oral presentation and 62 short papers for poster presentation in the program.
Welcome to the proceedings of GCC2004 and the city of Wuhan. Grid computing has become a mainstream research area in computer science and the GCC conference has become one of the premier forums for presentation of new...
详细信息
ISBN:
(数字)9783540302087
ISBN:
(纸本)9783540235644
Welcome to the proceedings of GCC2004 and the city of Wuhan. Grid computing has become a mainstream research area in computer science and the GCC conference has become one of the premier forums for presentation of new and exciting research in all aspectsofgridandcooperativecomputing. Theprogramcommitteeispleasedtopresent the proceedings of the 3rd International Conference on Grid and Cooperative Comp- ing (GCC2004), which comprises a collection of excellent technical papers, posters, workshops, and keynote speeches. The papers accepted cover a wide range of exciting topics, including resource grid and service grid, information grid and knowledge grid, grid monitoring,managementand organizationtools, grid portal, grid service, Web s- vices and their QoS, service orchestration, grid middleware and toolkits, software glue technologies, grid security, innovative grid applications, advanced resource reservation andscheduling,performanceevaluationandmodeling,computer-supportedcooperative work, P2P computing, automatic computing, and meta-information management. The conference continues to grow and this year a record total of 581 manuscripts (including workshop submissions) were submitted for consideration. Expecting this growth, the size of the program committee was increased from 50 members for GCC 2003 for 70 in GCC 2004. Relevant differences from previous editions of the conf- ence: it is worth mentioning a signi?cant increase in the number of papers submitted by authors from outside China; and the acceptance rate was much lower than for p- vious GCC conferences. From the 427 papers submitted to the main conference, the program committee selected only 96 regular papers for oral presentation and 62 short papers for poster presentation in the program.
暂无评论