{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:15Z","timestamp":1759638195120},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01759065","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"624-657","source":"Crossref","is-referenced-by-count":10,"title":["Finding a minimal cover for binary images: An optimal parallel algorithm"],"prefix":"10.1007","volume":"6","author":[{"given":"Dipen","family":"Moitra","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01759065_CR1","unstructured":"L. J. Aupperle, An Algorithm for Covering Polygons with Squares, Draft, Department of Computer Science., Princeton University, October 1988."},{"key":"BF01759065_CR2","unstructured":"L. J. Aupperle, H. E. Conn, J. M. Keil, and J. O'Rourke, Covering Orhogonal Polygons with Squares, Presented at the 26th Ann. Allerton Conf. on Communications, Control and Computing, Urbana, IL, 28\u201330 September 1988 (also Report HU-88\/16, Johns Hopkins University)."},{"key":"BF01759065_CR3","unstructured":"G. Blelloch, Scans as primitive parallel operations,Proc. Int. Conf. on Parallel Processing, pp. 355\u2013362, 1987."},{"key":"BF01759065_CR4","unstructured":"R. Cole and U. Vishkin, Faster optimal parallel prefix sums and list ranking, submitted toInformation and Computation (also Report CS-TR-277, Courant Institute)."},{"key":"BF01759065_CR5","doi-asserted-by":"crossref","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 Journal on Computing, vol. 17, No. 1, pp. 128\u2013142, Feb. 88.","DOI":"10.1137\/0217009"},{"key":"BF01759065_CR6","unstructured":"H. E. Conn and J. O'Rourke, Some Restricted Rectangle Covering Problems, Technical Report JHU-87\/13, Department of Computer Science, Johns Hopkins University. June 1987."},{"issue":"no. 1","key":"BF01759065_CR7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. Cook","year":"1986","unstructured":"S. Cook, C. Dwork, and R. Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes,SIAM Journal on Computing, vol. 15, no. 1, pp. 87\u201397, Feb. 1986.","journal-title":"SIAM Journal on Computing"},{"key":"BF01759065_CR8","doi-asserted-by":"crossref","unstructured":"J. C. Culberson and R. A. Reckhow, Covering polygons is hard,Proc. 29th Symp. on Foundations of Computer Science, pp. 601\u2013611, Oct. 1988.","DOI":"10.1109\/SFCS.1988.21976"},{"key":"BF01759065_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"E. Dekel and S. Sahni, A parallel matching algorithm for convex bipartite graphs and applications to scheduling,Journal of Parallel and Distributed Computing, vol. 1, pp. 185\u2013205, 1984.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"BF01759065_CR10","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/0734-189X(84)90139-7","volume":"28","author":"L. Ferrari","year":"1984","unstructured":"L. Ferrari, P. V. Sankar, and J. Sklansky, Minimal rectangular partitions of digitized blobs,Computer Vision, Graphics, and Image Processing, vol. 28, pp. 58\u201371, Oct. 1984.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"BF01759065_CR11","doi-asserted-by":"crossref","unstructured":"D. S. Franzblau and D. J. Kleitman, An algorithm for constructing regions with rectangles: independence and minimum generating sets for collections of intervals,Proc. 16th Ann. ACM Symp. on Theory of Computing, pp. 167\u2013174, 1984.","DOI":"10.1145\/800057.808678"},{"issue":"no. 2","key":"BF01759065_CR12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph,SIAM Journal on Computing, vol. 1, no. 2, pp. 180\u2013187, June 1972.","journal-title":"SIAM Journal on Computing"},{"key":"BF01759065_CR13","volume-title":"The Connection Machine","author":"W. D. Hillis","year":"1985","unstructured":"W. D. Hillis,The Connection Machine, MIT Press, Cambridge, MA, 1985."},{"issue":"no. 10","key":"BF01759065_CR14","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"34","author":"C. P. Kruskal","year":"1985","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, The power of parallel prefix,IEEE Transactions on Computers, vol. 34, no. 10, pp. 965\u2013968, Oct. 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"BF01759065_CR15","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fisher, Parallel prefix computation,Journal of the ACM, vol. 27, pp. 831\u2013838, Oct. 1980.","journal-title":"Journal of the ACM"},{"key":"BF01759065_CR16","unstructured":"H. Li and M. Maresca, Polymorphic-torus network,Proc. Int. Conf. on Parallel Processing, pp. 411\u2013414, 1987."},{"key":"BF01759065_CR17","unstructured":"W. J. Masek, Some NP-complete Set Covering Problems, Unpublished manuscript, MIT, 1979."},{"key":"BF01759065_CR18","unstructured":"D. Moitra, Efficient Parallel Algorithms for Covering Binary Images, Ph.D. thesis, Cornell University, May 1989."},{"key":"BF01759065_CR19","unstructured":"A. G. Ranade, Fluent Parallel Computation, Ph.D. thesis, Yale University, May 1989."},{"key":"BF01759065_CR20","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H. Samet","year":"1984","unstructured":"H. Samet, The quadtree and related hierarchical data structures,ACM Computing Surveys, vol. 16, pp. 187\u2013260, 1984.","journal-title":"ACM Computing Surveys"},{"issue":"no. 5","key":"BF01759065_CR21","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1145\/5689.5692","volume":"29","author":"D. S. Scott","year":"1986","unstructured":"D. S. Scott and S. S. Iyengar, TID: a translation invariant data structure for storing images,Communications of the ACM, vol. 29, no. 5, pp. 418\u2013429, May 1986.","journal-title":"Communications of the ACM"},{"key":"BF01759065_CR22","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0146-664X(75)80003-7","volume":"4","author":"S. L. Tanimoto","year":"1975","unstructured":"S. L. Tanimoto and T. Pavlidis, A hierarchical data structure for picture processing,Computer Graphics and Image Processing, vol. 4, pp. 104\u2013119, 1975.","journal-title":"Computer Graphics and Image Processing"},{"key":"BF01759065_CR23","series-title":"Technical Report 541","volume-title":"Covering polygons with squares","author":"R. Bar Yehuda","year":"1989","unstructured":"R. Bar Yehuda and E. Ben Chanoch, Covering polygons with squares, Technical Report 541, Computer Science Department, Technion, March 1989."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759065.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759065\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:22Z","timestamp":1586287642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":23,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759065"],"URL":"https:\/\/doi.org\/10.1007\/bf01759065","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}