{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T20:49:00Z","timestamp":1770324540018,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/bf02523677","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:50:25Z","timestamp":1162961425000},"page":"331-356","source":"Crossref","is-referenced-by-count":21,"title":["Complexities of efficient solutions of rectilinear polygon cover problems"],"prefix":"10.1007","volume":"17","author":[{"given":"P.","family":"Berman","sequence":"first","affiliation":[]},{"given":"B.","family":"DasGupta","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02523677_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and Hardness of Approximation Problems.Proc. 33rd IEEE Symp. on Foundations of Computer Science (FOCS) 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"BF02523677_CR2","unstructured":"P. Berman and B. DasGupta. Results on Approximation of the Rectilinear Polygon Cover Problems. Tech. Rep. #CS-92-06, Pennsylvania State University, June, 1992."},{"key":"BF02523677_CR3","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger. On the Complexity of Approximating the Independent Set Problem.Inform. and Comput., 96 (1992), 77\u201394.","journal-title":"Inform. and Comput."},{"key":"BF02523677_CR4","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1137\/0602042","volume":"2","author":"S. Chaiken","year":"1981","unstructured":"S. Chaiken, D. J. Kleitman, M. Saks, and J. Shearer. Covering Regions by Rectangles.SIAM J. Algebraic Discrete Methods, 2 (1981), 394\u2013410.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"BF02523677_CR5","unstructured":"H. E. Conn and J. O'Rourke. Some Restricted Rectangle Covering Problems. Tech Rep. JHU-87\/13, Johns Hopkins University, Baltimore, MD, 1987. Also appeared inProc. Allerton Conference, 1987, pp. 898\u2013907."},{"key":"BF02523677_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Corman","year":"1990","unstructured":"T. H. Corman, C. E. Leiserson, and R. L. Rivest.Introduction to Algorithms. MIT Press, Cambridge, MA 1990."},{"key":"BF02523677_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jagm.1994.1025","volume":"17","author":"J. C. Culberson","year":"1994","unstructured":"J. C. Culberson and R. A. Reckhow. Covering Polygon Is Hard.J. Algorithms, 17 (1994), 2\u201344.","journal-title":"J. Algorithms"},{"key":"BF02523677_CR8","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/0402027","volume":"2","author":"D. S. Franzblau","year":"1989","unstructured":"D. S. Franzblau. Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles.SIAM J. Discrete Math., 2 (1989), 307\u2013321.","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"BF02523677_CR9","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/S0019-9958(84)80012-1","volume":"63","author":"D. S. Franzblau","year":"1984","unstructured":"D. S. Franzblau and D. J. Kleitman. An Algorithm for Covering Polygons with Rectangles.Inform. and Control, 63(3) (1984), 164\u2013189.","journal-title":"Inform. and Control"},{"key":"BF02523677_CR10","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson.Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979."},{"key":"BF02523677_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and R. M. Karp. Ann\n                           5\/2 Algorithm for Maximum Matching in Bipartite Graphs.SIAM J. Comput., 2 (1979), 225\u2013231.","journal-title":"SIAM J. Comput."},{"key":"BF02523677_CR12","volume-title":"Ordering and Some Combinatorial Optimization Problems with Some Geometric Applications","author":"A. Lubiw","year":"1985","unstructured":"A. Lubiw. Ordering and Some Combinatorial Optimization Problems with Some Geometric Applications. Ph.D. Thesis, University of Waterloo, Ontario, 1985."},{"key":"BF02523677_CR13","volume-title":"The Boolean Basis Problem and How to Cover Polygons by Rectangles","author":"A. Lubiw","year":"1988","unstructured":"A. Lubiw. The Boolean Basis Problem and How to Cover Polygons by Rectangles. Manuscript, University of Waterloo, Ontario, 1988. Referenced in [8]. D. S. Franzblau. Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles.SIAM J. Discrete Math., 2 (1989), 307\u2013321."},{"key":"BF02523677_CR14","unstructured":"W. J. Masek. Some NP-Complete Set Covering Problems. Unpublished manuscript, MIT, Cambridge, MA. Referenced in [10]. M. R. Garey and D. S. Johnson.Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979."},{"key":"BF02523677_CR15","volume-title":"Introduction to VLSI Systems","author":"C. Mead","year":"1980","unstructured":"C. Mead and L. Conway.Introduction to VLSI Systems. Addison-Wesley, Reading, MA, 1980, Chapters 2 and 4."},{"key":"BF02523677_CR16","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/0402033","volume":"2","author":"R. Motwani","year":"1989","unstructured":"R. Motwani, A. Raghunathan, and H. Saran. Perfect Graphs and Orthogonally Convex Covers.SIAM J. Discrete Math., 2 (1989), 371\u2013392.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02523677_CR17","unstructured":"T. Ohtsuki. Minimum Dissection of Rectilinear Polygons.Proc. IEEE Symp. on Circuits and Systems, 1982, pp. 1210\u20131213."},{"key":"BF02523677_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J. O'Rourke","year":"1983","unstructured":"J. O'Rourke and K. J. Supowit. Some NP-Hard Polygon Decomposition Problems.IEEE Trans. Inform. Theory, 29 (1983), 181\u2013190.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"BF02523677_CR19","first-page":"211","volume":"2","author":"L. Pagli","year":"1979","unstructured":"L. Pagli, E. Lodi, F. Luccio, C. Mugnai, and W. Lipski. On Two-Dimensional Data Organization 2.Fund. Inform., 2 (1979), 211\u2013226.","journal-title":"Fund. Inform."},{"key":"BF02523677_CR20","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes.J. Computer System Sci., 43 (1991), 425\u2013440.","journal-title":"J. Computer System Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523677.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02523677\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523677.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,15]],"date-time":"2022-05-15T01:20:50Z","timestamp":1652577650000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02523677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02523677"],"URL":"https:\/\/doi.org\/10.1007\/bf02523677","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}