{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:21Z","timestamp":1725663621534},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540572732"},{"type":"electronic","value":"9783540480327"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57273-2_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:36:48Z","timestamp":1330259808000},"page":"109-120","source":"Crossref","is-referenced-by-count":1,"title":["Optimal CREW-PRAM algorithms for direct dominance problems"],"prefix":"10.1007","author":[{"given":"Amitava","family":"Datta","sequence":"first","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg-R\u00fcdiger","family":"Sack","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, D. Kravets, J. Park and S. Sen. Parallel searching in generalized Monge arrays with applications. Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 259\u2013268.","DOI":"10.1145\/97444.97693"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and S. Suri. Fast algorithms for computing the largest empty rectangle. Proc. 3rd Annual ACM Symp. on Comp. Geom., 1987, pp. 278\u2013290.","DOI":"10.1145\/41958.41988"},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","volume":"18","author":"M. Atallah","year":"1989","unstructured":"M. Atallah, R. Cole and M. Goodrich. Cascading divide-and-conquer: a technique for designing parallel algorithms. SIAM J. Computing, 18 (1989), pp. 499\u2013532.","journal-title":"SIAM J. Computing"},{"key":"10_CR4","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(86)90071-5","volume":"13","author":"M. Atallah","year":"1986","unstructured":"M. Atallah and G. Fredrickson. A note on finding the maximum empty rectangle. Discrete Applied Mathematics. 13 (1986) pp. 87\u201391.","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF01553888","volume":"4","author":"M. Atallah","year":"1989","unstructured":"M. Atallah and S. R. Kosaraju. An efficient algorithm for maxdorninance, with applications. Algorithmica 4 (1989) pp. 221\u2013236.","journal-title":"Algorithmica"},{"key":"10_CR6","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM J. Computing, 17, (1988), pp. 770\u2013785.","journal-title":"SIAM J. Computing"},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle, R. Drysdale and D. T. Lee. Computing the largest empty rectangle. SIAM J. Computing 15 (1986), pp. 300\u2013315.","journal-title":"SIAM J. Computing"},{"key":"10_CR8","first-page":"375","volume":"557","author":"I. W. Chen","year":"1991","unstructured":"I. W. Chen and D. K. Friesen. Parallel algorithms for some dominance problems based on a CREW PRAM. Proc. 2nd International Symposium on Algorithms, LNCS 557, 1991, pp. 375\u2013384.","journal-title":"LNCS"},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01762121","volume":"3","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3 (1988), pp. 329\u2013346.","journal-title":"Algorithmica"},{"key":"10_CR10","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. Approximate parallel scheduling, Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Computing, 17 (1988), pp. 128\u2013142.","journal-title":"SIAM J. Computing"},{"key":"10_CR11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0255(92)90115-O","volume":"64","author":"A. Datta","year":"1992","unstructured":"A. Datta. Efficient algorithms for the largest rectangle problem. Information Sciences, 64 (1992), pp. 121\u2013141.","journal-title":"Information Sciences"},{"key":"10_CR12","first-page":"344","volume":"III","author":"A. Datta","year":"1990","unstructured":"A. Datta and K. Krithivasan. Efficient algorithms for the maximum empty rectangle problem in shared memory and other architectures. Proc. 1990 International Conference on Parallel Processing, 1990, III, pp. 344\u2013345.","journal-title":"Proc. 1990 International Conference on Parallel Processing"},{"key":"10_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0255(92)90077-L","volume":"65","author":"L. Gewali","year":"1992","unstructured":"L. Gewali, M. Keil, S. Ntafos, On Covering Orthogonal Polygons with Star-Shaped Polygons. Information Sciences, 65 (1992), pp. 45\u201363.","journal-title":"Information Sciences"},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1137\/0220047","volume":"20","author":"M. T. Goodrich","year":"1991","unstructured":"M. T. Goodrich. Intersecting line segments in parallel with an output-sensitive number of processors. SIAM J. Computing, 20, (1991), pp. 737\u2013755.","journal-title":"SIAM J. Computing"},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/0196-6774(89)90011-4","volume":"10","author":"R. G\u00fcting","year":"1989","unstructured":"R. G\u00fcting, O. Nurmi and T. Ottmann. Fast algorithms for direct enclosures and direct dominances. J. Algorithms 10 (1989), pp. 170\u2013186.","journal-title":"J. Algorithms"},{"key":"10_CR16","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran, Parallel Algorithms for Shared-Memory Machines, Handbook of Theoretical Computer Science, Ed. J. van Leeuwen, Vol 1, Elsevier Science Publishers B.V, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(84)90124-0","volume":"8","author":"A. Namaad","year":"1984","unstructured":"A. Namaad, W. Hsu and D. T. Lee. On maximum empty rectangle problem. Discrete Applied Mathematics 8 (1984), pp. 267\u2013277.","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01840377","volume":"5","author":"M. Orlowski","year":"1990","unstructured":"M. Orlowski. A new algorithm for the largest empty rectangle problem. Algorithmica 5 (1990), pp. 65\u201373.","journal-title":"Algorithmica"},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/0196-6774(88)90028-4","volume":"9","author":"M. Overmars","year":"1988","unstructured":"M. Overmars and D. Wood. On rectangular visibility. J. of Algorithms 9 (1988), pp. 372\u2013390.","journal-title":"J. of Algorithms"},{"key":"10_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985."},{"key":"10_CR22","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and Parallelization. SIAM. J. Computing, 17 (1988), pp. 1253\u20131262.","journal-title":"SIAM. J. Computing"},{"key":"10_CR23","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic parallel time. SIAM J. Computing, 14 (1985), pp. 862\u2013874.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms\u2014ESA '93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57273-2_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:10:41Z","timestamp":1605647441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57273-2_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540572732","9783540480327"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-57273-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}