{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T23:03:48Z","timestamp":1784070228978,"version":"3.55.0"},"publisher-location":"Singapore","reference-count":27,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819233083","type":"print"},{"value":"9789819233090","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T00:00:00Z","timestamp":1784073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T00:00:00Z","timestamp":1784073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-981-92-3309-0_1","type":"book-chapter","created":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T22:08:14Z","timestamp":1784066894000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bi-Perfect Graphs and\u00a0the\u00a0Approximability of\u00a0Maximum Balanced Biclique"],"prefix":"10.1007","author":[{"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wanchote","family":"Jiamjitrak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ly","family":"Orgo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minoo","family":"Zarsav","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,15]]},"reference":[{"key":"1_CR1","first-page":"3","volume":"30","author":"C Arbib","year":"1999","unstructured":"Arbib, C., Mosca, R., et al.: Polynomial algorithms for special cases of the balanced bipartite subgraph problem. JCMCC J. Comb. Math. Comb. Comput. 30, 3\u201322 (1999)","journal-title":"JCMCC J. Comb. Math. Comb. Comput."},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-642-31155-0_13","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"A Atminas","year":"2012","unstructured":"Atminas, A., Lozin, V.V., Razgon, I.: Linear time algorithm for computing a small biclique in graphs without long induced paths. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 142\u2013152. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31155-0_13"},{"issue":"1\u20133","key":"1_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(93)90354-V","volume":"114","author":"S Bellantoni","year":"1993","unstructured":"Bellantoni, S., Hartman, I.B.A., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity. Discret. Math. 114(1\u20133), 41\u201349 (1993)","journal-title":"Discret. Math."},{"key":"1_CR4","unstructured":"Chalermsook, P., Orgo, L., Zarsav, M.: On geometric bipartite graphs with asymptotically smallest zarankiewicz numbers. In: Proceedings of the 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) (2025, to appear)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., et al.: From gap-eth to FPT-inapproximability: clique, dominating set, and more. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 743\u2013754. IEEE (2017)","DOI":"10.1109\/FOCS.2017.74"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-030-60440-0_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P Chalermsook","year":"2020","unstructured":"Chalermsook, P., Jiamjitrak, W.P., Orgo, L.: On finding balanced bicliques via matchings. In: Adler, I., M\u00fcller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 238\u2013247. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-60440-0_19"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.endm.2016.10.029","volume":"55","author":"P Chalermsook","year":"2016","unstructured":"Chalermsook, P., Vaz, D.: A note on fractional coloring and the integrality gap of LP for maximum weight independent set. Electron. Notes Discret. Math. 55, 113\u2013116 (2016)","journal-title":"Electron. Notes Discret. Math."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 860\u2013868. SIAM (2021)","DOI":"10.1137\/1.9781611976465.54"},{"key":"1_CR9","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Keller, C., Smorodinsky, S.: On Zarankiewicz\u2019s problem for intersection hypergraphs of geometric objects. In: Aichholzer, O., Wang, H. (eds.) 41st International Symposium on Computational Geometry, SoCG 2025, 23\u201327 June 2025, Kanazawa, Japan. LIPIcs, vol. 332, pp. 33:1\u201333:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2025.33","DOI":"10.4230\/LIPIcs.SoCG.2025.33"},{"key":"1_CR10","unstructured":"Cheng, Y., Church, G.M.: Biclustering of expression data. In: ISMB, vol. 8, pp. 93\u2013103 (2000)"},{"issue":"6","key":"1_CR11","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4171\/JEMS\/705","volume":"19","author":"J Fox","year":"2017","unstructured":"Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz\u2019s problem. J. Eur. Math. Soc. 19(6), 1785\u20131810 (2017). https:\/\/doi.org\/10.4171\/JEMS\/705","journal-title":"J. Eur. Math. Soc."},{"key":"1_CR12","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer (2012)"},{"issue":"1","key":"1_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"IB-A Hartman","year":"1991","unstructured":"Hartman, I.B.-A., Newman, I., Ziv, R.: On grid intersection graphs. Discret. Math. 87(1), 41\u201352 (1991)","journal-title":"Discret. Math."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\varepsilon }$$. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 627\u2013636. IEEE (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"key":"1_CR15","doi-asserted-by":"publisher","unstructured":"Keller, C., Smorodinsky, S.: Zarankiewicz\u2019s problem via $$\\epsilon $$-t-nets. In: Mulzer, W., Phillips, J.M. (eds.) 40th International Symposium on Computational Geometry, SoCG 2024, 11\u201314 June 2024, Athens, Greece. LIPIcs, vol. 293, pp. 66:1\u201366:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2024.66","DOI":"10.4230\/LIPIcs.SoCG.2024.66"},{"issue":"1\u20133","key":"1_CR16","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(94)00054-H","volume":"60","author":"B Klinz","year":"1995","unstructured":"Klinz, B., Rudolf, R., Woeginger, G.J.: Permuting matrices to avoid forbidden submatrices. Discret. Appl. Math. 60(1\u20133), 223\u2013248 (1995)","journal-title":"Discret. Appl. Math."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"K\u0151v\u00e1ri, T., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3, 50\u201357 (1954). http:\/\/eudml.org\/doc\/210011","DOI":"10.4064\/cm-3-1-50-57"},{"issue":"5","key":"1_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"Lin, B.: The parameterized complexity of the k-biclique problem. J. ACM (JACM) 65(5), 1\u201323 (2018)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"1_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Lubiw, A.: Doubly lexical orderings of matrices. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 396\u2013404 (1985)","DOI":"10.1145\/22145.22189"},{"key":"1_CR21","doi-asserted-by":"publisher","unstructured":"Manurangsi, P.: Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms 11(1) (2018). http:\/\/www.mdpi.com\/1999-4893\/11\/1\/10. https:\/\/doi.org\/10.3390\/a11010010","DOI":"10.3390\/a11010010"},{"key":"1_CR22","unstructured":"Manurangsi, P., Rubinstein, A., Schramm, T.: The strongish planted clique hypothesis and its consequences. In: ITCS (2021)"},{"issue":"2\u20133","key":"1_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H M\u00fcller","year":"1987","unstructured":"M\u00fcller, H., Brandst\u00e4dt, A.: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoret. Comput. Sci. 53(2\u20133), 257\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1_CR24","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1137\/0217045","volume":"17","author":"SS Ravi","year":"1988","unstructured":"Ravi, S.S., Lloyd, E.L.: The complexity of near-optimal programmable logic array folding. SIAM J. Comput. 17(4), 696\u2013710 (1988)","journal-title":"SIAM J. Comput."},{"issue":"15","key":"1_CR25","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1016\/j.dam.2010.06.002","volume":"158","author":"AMS Shrestha","year":"2010","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: On orthogonal ray graphs. Discret. Appl. Math. 158(15), 1650\u20131659 (2010)","journal-title":"Discret. Appl. Math."},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Uehara, R.: Linear time algorithms on chordal bipartite and strongly chordal graphs. In: International Colloquium on Automata, Languages, and Programming, pp. 993\u20131004. Springer (2002)","DOI":"10.1007\/3-540-45465-9_85"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-92-3309-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T22:08:16Z","timestamp":1784066896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-92-3309-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,15]]},"ISBN":["9789819233083","9789819233090"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-981-92-3309-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,15]]},"assertion":[{"value":"15 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/event.ntu.edu.sg\/cocoon2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}