{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:19Z","timestamp":1759638979901},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_20","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"184-193","source":"Crossref","is-referenced-by-count":3,"title":["Bisections above Tight Lower Bounds"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Mnich","sequence":"first","affiliation":[]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1016\/j.ipl.2010.08.001","volume":"110","author":"G. Gutin","year":"2010","unstructured":"Gutin, G., Yeo, A.: Note on maximal bisection above tight lower bound. Information Processing Letters\u00a0110, 966\u2013969 (2010)","journal-title":"Information Processing Letters"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. Journal of Computer and System Sciences\u00a062, 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"25","author":"C.S. Edwards","year":"1973","unstructured":"Edwards, C.S.: Some extremal properties of bipartite subgraphs. Canadian Journal of Mathematics\u00a025, 475\u2013485 (1973)","journal-title":"Canadian Journal of Mathematics"},{"key":"20_CR6","unstructured":"Edwards, C.S.: An improved lower bound for the number of edges in a largest bipartite subgraph. In: Recent Advances in Graph Theory (Proceedings of Second Czechoslovak Symposium, Prague, 1974), Prague, pp. 167\u2013181 (1975)"},{"key":"20_CR7","unstructured":"Lee, C., Loh, P.S., Sudakov, B.: Bisections of graphs (2011), \n                    \n                      http:\/\/arxiv.org\/abs\/1109.3180\/v3"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N. Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica\u00a061, 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"20_CR9","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomass\u00e9, S., Yeo, A.: Simultaneously Satisfying Linear Equations Over \n                    \n                      \n                    \n                    $\\mathbb F_2$\n                  : MaxLin2 and Max-r-Lin2 Parameterized Above Average. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a013, pp. 229\u2013240 (2011)"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jcss.2011.01.004","volume":"78","author":"G. Gutin","year":"2012","unstructured":"Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. Journal of Computer and System Sciences\u00a078, 151\u2013163 (2012)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/978-3-642-31594-7_21","volume-title":"ICALP 2012","author":"R. Crowston","year":"2012","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-Cut Parameterized above the Edwards-Erd\u0151s Bound. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, part I. LNCS, vol.\u00a07391, pp. 242\u2013253. Springer, Heidelberg (2012)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-30891-8_14","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"G. Gutin","year":"2012","unstructured":"Gutin, G., Yeo, A.: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol.\u00a07370, pp. 257\u2013286. Springer, Heidelberg (2012)"},{"key":"20_CR13","unstructured":"Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer (2003)"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/12.67327","volume":"40","author":"D.J. Haglin","year":"1991","unstructured":"Haglin, D.J., Venkatesan, S.M.: Approximation and intractability results for the maximum cut problem and its variants. IEEE Transactions on Computing\u00a040, 110\u2013113 (1991)","journal-title":"IEEE Transactions on Computing"},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ejor.2010.11.010","volume":"210","author":"B. Ries","year":"2011","unstructured":"Ries, B., Zenklusen, R.: A 2-approximation for the maximum satisfying bisection problem. European Journal of Operational Research\u00a0210, 169\u2013175 (2011)","journal-title":"European Journal of Operational Research"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:00:42Z","timestamp":1620133242000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}