{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:05:25Z","timestamp":1773655525179,"version":"3.50.1"},"reference-count":18,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"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":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.3103\/s0146411617070276","type":"journal-article","created":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T03:40:46Z","timestamp":1518666046000},"page":"576-585","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Polyhedral Characteristics of Balanced and Unbalanced Bipartite Subgraph Problems"],"prefix":"10.3103","volume":"51","author":[{"given":"V. A.","family":"Bondarenko","sequence":"first","affiliation":[]},{"given":"A. V.","family":"Nikolaev","sequence":"additional","affiliation":[]},{"given":"D. A.","family":"Shovgenov","sequence":"additional","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2018,2,7]]},"reference":[{"key":"6658_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"N. Apollonio","year":"2014","unstructured":"Apollonio, N. and Simeone, B., The maximum vertex coverage problem on bipartite graphs, Discrete Appl. Math., 2014, vol. 165, pp. 37\u201348.","journal-title":"Discrete Appl. Math."},{"key":"6658_CR2","first-page":"3","volume":"39","author":"C. Arbib","year":"1999","unstructured":"Arbib, C. and Mosca, R., Polynomial algorithms for special cases of the balanced complete bipartite subgraph problem, J. Comb. Math. Comb. Comput., 1999, vol. 39, pp. 3\u201322.","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"9","key":"6658_CR3","first-page":"1137","volume":"44","author":"V.A. Bondarenko","year":"1983","unstructured":"Bondarenko, V.A., Nonpolynomial lowerbound of the traveling salesman problem complexity in one class of algorithms, Autom. Remote Control, 1983, vol. 44, no. 9, pp. 1137\u20131142.","journal-title":"Autom. Remote Control"},{"key":"6658_CR4","volume-title":"Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoi optimizatsii","author":"V.A. Bondarenko","year":"2008","unstructured":"Bondarenko, V.A. and Maksimenko, A.N., Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoi optimizatsii (Geometric Constructions and Complexity in Combinatorial Optimization), Moscow: LKI, 2008."},{"issue":"2","key":"6658_CR5","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1134\/S1064562413050062","volume":"88","author":"V.A. Bondarenko","year":"2013","unstructured":"Bondarenko, V.A. and Nikolaev, A.V., Combinatorial and geometric properties of the max-cut and min-cut problems, Dokl. Math., 2013, vol. 88, no. 2, pp. 516\u2013517.","journal-title":"Dokl. Math."},{"key":"6658_CR6","volume-title":"Int. J. Math. Math. Sci.","author":"V. Bondarenko","year":"2016","unstructured":"Bondarenko, V. and Nikolaev, A., On graphs of the cone decompositions for the min-cut and max-cut problems, Int. J. Math. Math. Sci., 2016, vol. 2016."},{"issue":"4","key":"6658_CR7","doi-asserted-by":"publisher","first-page":"453","DOI":"10.18255\/1818-1015-2015-4-453-463","volume":"22","author":"V.A. Bondarenko","year":"2015","unstructured":"Bondarenko, V.A., Nikolaev, A.V., and Shovgenov, D.A., 1-skeletons of the spanning tree problems with additional constraints, Model. Anal. Inf. Syst., 2015, vol. 22, no. 4, pp. 453\u2013463.","journal-title":"Model. Anal. Inf. Syst."},{"key":"6658_CR8","first-page":"93","volume-title":"Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology","author":"Y. Cheng","year":"2000","unstructured":"Cheng, Y. and Church, G.M., Biclustering of expression data, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000, pp. 93\u2013103"},{"key":"6658_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R. Diestel","year":"2010","unstructured":"Diestel, R., Graph Theory, Springer-Verlag Berlin Heidelberg, 2010."},{"key":"6658_CR10","volume-title":"Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem. Tech. Rep. MCS04-04","author":"U. Feige","year":"2004","unstructured":"Feige, U. and Kogan, S., Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem. Tech. Rep. MCS04-04, The Weizmann Inst. of Science, 2004."},{"key":"6658_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, NY: W. H. Freeman & Co, 1979."},{"key":"6658_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lovasz, L., and Schrijver, A., Geometric Algorithms and Combinatorial Optimization, Springer-Verlag Berlin Heidelberg, 1993."},{"issue":"3","key":"6658_CR13","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","volume":"8","author":"D.S. Johnson","year":"1987","unstructured":"Johnson, D.S., The NP-completeness column: An ongoing guide, J. Algorithms, 1987, vol. 8, no. 3, pp. 438\u2013448.","journal-title":"J. Algorithms"},{"issue":"2","key":"6658_CR14","first-page":"143","volume":"17","author":"G. Joret","year":"2015","unstructured":"Joret, G. and Vetta, A., Reducing the rank of a matroid, Discrete Math. Theor. Comput. Sci., 2015, vol. 17, no. 2, pp. 143\u2013156.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"4","key":"6658_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E. and Karp, R.M., An n5\/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 1973, vol. 2, no. 4, pp. 225\u2013231.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6658_CR16","first-page":"1611","volume":"88","author":"A.N. Maksimenko","year":"2013","unstructured":"Maksimenko, A.N., Combinatorial properties of the polyhedron associated with the shortest path problem, Comput. Math. Math. Phys., 2013, vol. 88, no. 2, pp. 1611\u20131614.","journal-title":"Comput. Math. Math. Phys."},{"issue":"5","key":"6658_CR17","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ipl.2009.11.015","volume":"110","author":"D. Mubayi","year":"2010","unstructured":"Mubayi, D. and Tur\u00e0n, G., Finding bipartite subgraphs efficiently, Inf. Process. Lett., 2010, vol. 110, no. 5, pp. 174\u2013177.","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"6658_CR18","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1137\/0217045","volume":"17","author":"S.S. Ravi","year":"1988","unstructured":"Ravi, S.S. and Lloyd, E.L., The complexity of near-optimal programmable logic array folding, SIAM J. Comput., 1988, vol. 17, no. 4, pp. 696\u2013710.","journal-title":"SIAM J. Comput."}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411617070276","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411617070276.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411617070276.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T21:57:47Z","timestamp":1773611867000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411617070276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":18,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["6658"],"URL":"https:\/\/doi.org\/10.3103\/s0146411617070276","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]},"assertion":[{"value":"15 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}