{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:44:54Z","timestamp":1773085494577,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,1,6]],"date-time":"2011-01-06T00:00:00Z","timestamp":1294272000000},"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":[[2012,10]]},"DOI":"10.1007\/s00453-010-9486-x","type":"journal-article","created":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T16:01:12Z","timestamp":1294243272000},"page":"311-325","source":"Crossref","is-referenced-by-count":16,"title":["Finding Maximum Edge Bicliques in Convex Bipartite Graphs"],"prefix":"10.1007","volume":"64","author":[{"given":"Doron","family":"Nussbaum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuye","family":"Pu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg-R\u00fcdiger","family":"Sack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamid","family":"Zarrabi-Zadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,6]]},"reference":[{"issue":"1\u20134","key":"9486_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1\u20134), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"issue":"1","key":"9486_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.dam.2003.09.004","volume":"145","author":"G. Alexe","year":"2004","unstructured":"Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discrete Appl. Math. 145(1), 11\u201321 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"3\u20134","key":"9486_CR3","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1089\/10665270360688075","volume":"10","author":"A. Ben-Dor","year":"2003","unstructured":"Ben-Dor, A., Chor, B., Karp, R., Yakhini, Z.: Discovering local structure in gene expression data: the order-preserving submatrix problem. J. Comput. Biol. 10(3\u20134), 373\u2013384 (2003)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"9486_CR4","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. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9486_CR5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"9486_CR6","first-page":"406","volume-title":"Proceedings of the 32nd Symposium on Mathematical Foundations of Computer Science","author":"G. Brodal","year":"2007","unstructured":"Brodal, G., Georgiadis, L., Hansen, K., Katriel, I.: Dynamic matchings in convex bipartite graphs. In: Proceedings of the 32nd Symposium on Mathematical Foundations of Computer Science, pp. 406\u2013417 (2007)"},{"key":"9486_CR7","first-page":"93","volume-title":"Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology","author":"Y. Chen","year":"2000","unstructured":"Chen, Y., Church, G.: Biclustering of expression data. In: Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, pp. 93\u2013103 (2000)"},{"issue":"1\u20132","key":"9486_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0925-7721(95)00041-0","volume":"7","author":"K. Daniels","year":"1997","unstructured":"Daniels, K., Milenkovic, V., Roth, D.: Finding the largest area axis-parallel rectangle in a polygon. Comput. Geom. Theory Appl. 7(1\u20132), 125\u2013148 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"9486_CR9","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1006\/jagm.2001.1199","volume":"41","author":"M. Dawande","year":"2001","unstructured":"Dawande, M., Keskinocak, P., Swaminathan, J.M., Tayur, S.: On bipartite and multipartite clique problems. J. Algorithms 41(2), 388\u2013403 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20133","key":"9486_CR10","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2005.01.014","volume":"337","author":"V.M. Dias","year":"2005","unstructured":"Dias, V.M., de Figueiredo, C.M., Szwarcfiter, J.L.: Generating bicliques of a graph in lexicographic order. Theor. Comput. Sci. 337(1\u20133), 240\u2013248 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"14","key":"9486_CR11","doi-asserted-by":"crossref","first-page":"1826","DOI":"10.1016\/j.dam.2007.03.017","volume":"155","author":"V.M. Dias","year":"2007","unstructured":"Dias, V.M., de Figueiredo, C.M., Szwarcfiter, J.L.: On the generation of bicliques of a graph. Discrete Appl. Math. 155(14), 1826\u20131832 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9486_CR12","first-page":"534","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing","author":"U. Feige","year":"2002","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)"},{"issue":"4","key":"9486_CR13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0020-0190(87)90174-8","volume":"25","author":"O. Fries","year":"1987","unstructured":"Fries, O., Mehlhorn, K., N\u00e4her, S., Tsakalidis, A.: A log\u2009log\u2009n data structure for three-sided range queries. Inf. Process. Lett. 25(4), 269\u2013273 (1987)","journal-title":"Inf. Process. Lett."},{"key":"9486_CR14","volume-title":"Formal Concept Analysis, Mathematical Foundations","author":"B. Ganter","year":"1996","unstructured":"Ganter, B., Wille, R.: Formal Concept Analysis, Mathematical Foundations. Springer, Berlin (1996)"},{"key":"9486_CR15","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"7","key":"9486_CR16","doi-asserted-by":"crossref","first-page":"1447","DOI":"10.1016\/j.dam.2008.10.010","volume":"157","author":"A. G\u00e9ly","year":"2009","unstructured":"G\u00e9ly, A., Nourine, L., Sadi, B.: Enumeration aspects of maximal cliques and bicliques. Discrete Appl. Math. 157(7), 1447\u20131459 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9486_CR17","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F. Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. 14, 313\u2013316 (1967)","journal-title":"Nav. Res. Logist."},{"key":"9486_CR18","volume-title":"Technical Report 48, Electronic Colloquium on Computation Complexity","author":"A. Goerdt","year":"2004","unstructured":"Goerdt, A., Lanka, A.: An approximation hardness result for bipartite clique. In: Technical Report 48, Electronic Colloquium on Computation Complexity (2004)"},{"issue":"1\u20132","key":"9486_CR19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9486_CR20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(95)00027-A","volume":"55","author":"T. Kloks","year":"1995","unstructured":"Kloks, T., Kratsch, D.: Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph. Inf. Process. Lett. 55(1), 11\u201316 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9486_CR21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"Y.D. Liang","year":"1997","unstructured":"Liang, Y.D., Chang, M.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Inform. 34(5), 337\u2013346 (1997)","journal-title":"Acta Inform."},{"issue":"4","key":"9486_CR22","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski","year":"1981","unstructured":"Lipski, W., Preparata, F.P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15(4), 329\u2013346 (1981)","journal-title":"Acta Inform."},{"issue":"1","key":"9486_CR23","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/TCBB.2004.2","volume":"1","author":"S.C. Madeira","year":"2004","unstructured":"Madeira, S.C., Oliveira, A.L.: Biclustering algorithms for biological data analysis: a survey. IEEE ACM Trans. Comput. Biol. Bioinform. 1(1), 24\u201345 (2004)","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"issue":"1\u20133","key":"9486_CR24","doi-asserted-by":"crossref","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 Appl. Math. 88(1\u20133), 325\u2013354 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9486_CR25","first-page":"448","volume-title":"Proceedings of the 16th Annual Conference on Computational Learning Theory","author":"N. Mishra","year":"2003","unstructured":"Mishra, N., Ron, D., Swaminathan, R.: On finding large conjunctive clusters. In: Proceedings of the 16th Annual Conference on Computational Learning Theory, pp. 448\u2013462 (2003)"},{"issue":"3","key":"9486_CR26","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R. Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9486_CR27","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00453-007-9006-9","volume":"53","author":"J. Soares","year":"2009","unstructured":"Soares, J., Stefanes, M.: Algorithms for maximum independent set in convex bipartite graphs. Algorithmica 53(1), 35\u201349 (2009)","journal-title":"Algorithmica"},{"issue":"12","key":"9486_CR28","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G. Steiner","year":"1996","unstructured":"Steiner, G., Yeomans, J.S.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Comput. Appl. Math. 31(12), 91\u201396 (1996)","journal-title":"Comput. Appl. Math."},{"key":"9486_CR29","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1007\/978-3-540-79228-4_25","volume-title":"Theory and Applications of Models of Computation","author":"J. Tan","year":"2008","unstructured":"Tan, J.: Inapproximability of maximum weighted edge biclique and its applications. In: Theory and Applications of Models of Computation, pp. 282\u2013293 (2008)"},{"issue":"1","key":"9486_CR30","doi-asserted-by":"crossref","first-page":"S136","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136","volume":"18","author":"A. Tanay","year":"2002","unstructured":"Tanay, A., Sharan, R., Shamir, R.: Discovering statistically significant biclusters in gene expression data. Bioinformatics Suppl. 18(1), S136\u2013S144 (2002)","journal-title":"Bioinformatics Suppl."},{"issue":"1\u20132","key":"9486_CR31","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(94)00220-D","volume":"147","author":"C. Yu","year":"1995","unstructured":"Yu, C., Chen, G.: Efficient parallel algorithms for doubly convex-bipartite graphs. Theor. Comput. Sci. 147(1\u20132), 249\u2013265 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9486_CR32","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/71.481592","volume":"7","author":"C. Yu","year":"1996","unstructured":"Yu, C., Chen, G.: An efficient parallel recognition algorithm for bipartite-permutation graphs. IEEE Trans. Parallel Distrib. Syst. 7(1), 3\u201310 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9486-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9486-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9486-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9486-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,6]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9486"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9486-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,6]]}}}