{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:38Z","timestamp":1725514418549},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_62","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"680-691","source":"Crossref","is-referenced-by-count":1,"title":["Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Dom","sequence":"first","affiliation":[]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"62_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences\u00a013, 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"62_CR2","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating Minimum Vertex Cover. Annals of Mathematics\u00a0162(1), 439\u2013485 (2005)","journal-title":"Annals of Mathematics"},{"key":"62_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"62_CR4","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"62_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"1\u20132","key":"62_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., et al.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science\u00a0234(1\u20132), 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"key":"62_CR7","unstructured":"Hajiaghayi, M.T.: Consecutive ones property. Manuscript, University Waterloo, Canada (2000)"},{"issue":"3","key":"62_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00325-8","volume":"83","author":"M.T. Hajiaghayi","year":"2002","unstructured":"Hajiaghayi, M.T., Ganjali, Y.: A note on the consecutive ones submatrix problem. Information Processing Letters\u00a083(3), 163\u2013166 (2002)","journal-title":"Information Processing Letters"},{"issue":"4","key":"62_CR9","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"62_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"W.-L. Hsu","year":"2002","unstructured":"Hsu, W.-L.: A simple test for the consecutive ones property. Journal of Algorithms\u00a043, 1\u201316 (2002)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"62_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(02)00435-8","volume":"296","author":"W.-L. Hsu","year":"2003","unstructured":"Hsu, W.-L., McConnell, R.M.: PC trees and circular-ones arrangements. Theoretical Computer Science\u00a0296(1), 99\u2013116 (2003)","journal-title":"Theoretical Computer Science"},{"key":"62_CR12","first-page":"379","volume-title":"Proc.\u00a018th IEEE Annual Conference on Computational Complexity","author":"S. Khot","year":"2003","unstructured":"Khot, S., Regev, O.: Vertex Cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: Proc.\u00a018th IEEE Annual Conference on Computational Complexity, pp. 379\u2013386. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"62_CR13","first-page":"768","volume-title":"Proc. 15th ACM-SIAM SODA","author":"R.M. McConnell","year":"2004","unstructured":"McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: Proc. 15th ACM-SIAM SODA, pp. 768\u2013777. SIAM, Philadelphia (2004)"},{"key":"62_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0166-218X(98)00078-X","volume":"88","author":"J. Meidanis","year":"1998","unstructured":"Meidanis, J., Porto, O., Telles, G.P.: On the consecutive ones property. Discrete Applied Mathmatics\u00a088, 325\u2013354 (1998)","journal-title":"Discrete Applied Mathmatics"},{"key":"62_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"62_CR16","doi-asserted-by":"crossref","unstructured":"Tan, J., Zhang, L.: The consecutive ones submatrix problem for sparse matrices. To appear in Algorithmica. Preliminary version titled \u201cApproximation algorithms for the consecutive ones submatrix problem on sparse matrices\u201d appeared in Proc.\u00a015th ISAAC, LNCS vol. 3341, pp. 836\u2013846. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30551-4_71"},{"issue":"39","key":"62_CR17","doi-asserted-by":"crossref","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"2","author":"A.C. Tucker","year":"1971","unstructured":"Tucker, A.C.: Matrix characterizations of circular-arc graphs. Pacific Journal of Mathematics\u00a02(39), 535\u2013545 (1971)","journal-title":"Pacific Journal of Mathematics"},{"key":"62_CR18","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A.C. Tucker","year":"1972","unstructured":"Tucker, A.C.: A structure theorem for the consecutive 1\u2019s property. Journal of Combinatorial Theory (B)\u00a012, 153\u2013162 (1972)","journal-title":"Journal of Combinatorial Theory (B)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_62.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:29Z","timestamp":1619516309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_62","relation":{},"subject":[]}}