{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T16:29:57Z","timestamp":1770136197307,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540609223","type":"print"},{"value":"9783540497233","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_36","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:04:26Z","timestamp":1330272266000},"page":"439-452","source":"Crossref","is-referenced-by-count":4,"title":["A combinatorial design approach to MAXCUT"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Hofmeister","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanno","family":"Lefmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, Bipartite Subgraphs, preprint, 1995.","DOI":"10.1007\/BF01261315"},{"key":"36_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J. Spencer, The Probabilistic Method, Wiley & Sons, New York, 1992."},{"key":"36_CR3","unstructured":"I. Anderson, Combinatorial Designs, Construction Methods, Ellis Horwood, 1990."},{"key":"36_CR4","first-page":"259","volume":"16","author":"L. Andersen","year":"1983","unstructured":"L. Andersen, D. Grant and N. Linial, Extremal k-colourable Subgraphs, Ars Comb. 16, 1983, 259\u2013270.","journal-title":"Ars Comb."},{"key":"36_CR5","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger, and G. Reinelt, An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design, Operations Research 36, 1988, 493\u2013513.","journal-title":"Operations Research"},{"key":"36_CR6","series-title":"Coll. Math. Soc. J\u00e1nos Bolyai 10","first-page":"91","volume-title":"Finite and Infinite Sets","author":"Z. Baranyai","year":"1973","unstructured":"Z. Baranyai, On the Factorization of the Complete Uniform Hypergraph, in: Finite and Infinite Sets, eds. Hajnal, Rado, S\u00f3s, Coll. Math. Soc. J\u00e1nos Bolyai 10, North Holland, Amsterdam, 1973, 91\u2013107."},{"key":"36_CR7","first-page":"105","volume":"29","author":"T. Beth","year":"1974","unstructured":"T. Beth, Algebraische Aufl\u00f6sungsalgorithmen f\u00fcr einige unendliche Familien von 3-Designs, Le Math. 29, 1974, 105\u2013135.","journal-title":"Le Math."},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/BF01180606","volume":"34","author":"R. Breusch","year":"1931","unstructured":"R. Breusch, Zur Verallgemeinerung des Bertrandschen Postulates, dass zwischen x und 2x stets Primzahlen liegen, Math. Z. 34, 1931, 505\u2013526.","journal-title":"Math. Z."},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R. Brooks","year":"1941","unstructured":"R. Brooks, On Coloring the Nodes of a Network, Camb. Phil. Soc. 37, 1941, 194\u2013197.","journal-title":"Camb. Phil. Soc."},{"key":"36_CR10","first-page":"148","volume":"855","author":"J. D. Cho","year":"1994","unstructured":"J. D. Cho, S. Raje and M. Sarrafzadeh, Approximation Algorithm on Multi-Way Maxcut Partitioning, Proc. 2nd Europ. Symp. on Algorithms, Springer LNCS 855, 1994, 148\u2013158.","journal-title":"Springer LNCS"},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"25","author":"C. S. Edwards","year":"1973","unstructured":"C. S. Edwards, Some Extremal Properties of Bipartite Graphs, Can. J. Math. 25, 1973, 475\u2013485.","journal-title":"Can. J. Math."},{"key":"36_CR12","first-page":"167","volume-title":"Recent Advances in Graph Theory","author":"C. S. Edwards","year":"1975","unstructured":"C. S. Edwards, An Improved Lower Bound for the Number of Edges in a Largest Bipartite Subgraph, in: Recent Advances in Graph Theory, Academia, Prag, 1975, 167\u2013181."},{"key":"36_CR13","first-page":"283","volume":"18","author":"P. Erd\u00f6s","year":"1967","unstructured":"P. Erd\u00f6s, On Bipartite Subgraphs of Graphs, Math. Lapok 18, 1967, 283\u2013288.","journal-title":"Math. Lapok"},{"key":"36_CR14","unstructured":"P. Erd\u00f6s, Some Recent Problems in Combinatorics and Graph Theory, preprint, 1995; and Lecture at the 26th Southeastern Int. Conf. on Graph Theory, Combinatorics and Computing, Boca Raton, 1995."},{"key":"36_CR15","unstructured":"P. Erd\u00f6s, A. Gy\u00e1rf\u00e1s and Y. Kohayakawa, The Size of the Largest Bipartite Subgraphs, preprint, 1995."},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some Simplified NP-complete Graph Problems, Theo. Comp. Sci. 1, 1976, 237\u2013267.","journal-title":"Theo. Comp. Sci."},{"key":"36_CR17","first-page":"215","volume-title":"Combinatorics, Paul Erd\u00f6s is Eighty, Vol 1","author":"R. H\u00e4ggkvist","year":"1993","unstructured":"R. H\u00e4ggkvist and T. Hellgren, Extensions of Edge-Colorings in Hypergraphs I, in: Combinatorics, Paul Erd\u00f6s is Eighty, Vol 1, Bolyai Society, Budapest, 1993, 215\u2013238."},{"key":"36_CR18","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/12.67327","volume":"40","author":"D. J. Haglin","year":"1991","unstructured":"D. J. Haglin and S. M. Venkatesan, Approximation and Intractability Results for the Maximum Cut Problem and its Variants, IEEE Trans. Comp. 40, 1991, 110\u2013113.","journal-title":"IEEE Trans. Comp."},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0304-3975(89)90121-7","volume":"68","author":"H. Karloff","year":"1989","unstructured":"H. Karloff, An NC Algorithm for Brooks' Theorem, Theo. Comp. Sci. 68, 1989, 89\u2013103.","journal-title":"Theo. Comp. Sci."},{"key":"36_CR20","first-page":"343","volume":"903","author":"Y. Kajitani","year":"1994","unstructured":"Y. Kajitani, J. D. Cho, and M. Sarrafzadeh, New Approximation Results on Graph Matching and Related Problems, Proc. 20th Workshop on Graph Theoretic Concepts in Computer Science, Springer LNCS 903, 1994, 343\u2013358.","journal-title":"Proc. 20th Workshop on Graph Theoretic Concepts in Computer Science, Springer LNCS"},{"key":"36_CR21","first-page":"458","volume":"27","author":"J. X. Lu","year":"1984","unstructured":"J. X. Lu, An Existence Theorem for Resolvable Balanced Incomplete Block Designs, (in Chinese), Acta Math. Sin. 27, 1984, 458\u2013468.","journal-title":"Acta Math. Sin."},{"key":"36_CR22","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(92)90041-S","volume":"41","author":"J. Misra","year":"1992","unstructured":"J. Misra and D. Gries, A Constructive Version of Vizing's Theorem, Inf. Proc. Letters 41, 1992, 131\u2013133.","journal-title":"Inf. Proc. Letters"},{"key":"36_CR23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1017\/S0963548300000596","volume":"2","author":"N. Ngoc van","year":"1993","unstructured":"N. van Ngoc and Z. Tuza, Linear Time Approximation Algorithms for the Max Cut Problem, Comb., Prob. Comp. 2, 1993, 201\u2013210.","journal-title":"Comb., Prob. Comp."},{"key":"36_CR24","unstructured":"R. Peltesohn, Das Turnierproblem f\u00fcr Spiele zu je dreien, Dissertation, Berlin, 1936."},{"key":"36_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0012-365X(86)90192-5","volume":"58","author":"S. Poljak","year":"1986","unstructured":"S. Poljak and D. Turz\u00edk, A Polynomial Time Heuristic for Certain Subgraph Optimization Problems with Guaranteed Worst Case Bound, Disc. Math. 58, 1986, 99\u2013104.","journal-title":"Disc. Math."},{"key":"36_CR26","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/S0895480191196824","volume":"7","author":"S. Poljak","year":"1994","unstructured":"S. Poljak and Z. Tuza, Bipartite Subgraphs of Triangle-Free Graphs, SIAM J. Disc. Math. 7, 1994, 307\u2013313.","journal-title":"SIAM J. Disc. Math."},{"key":"36_CR27","doi-asserted-by":"crossref","unstructured":"S. Poljak and Z. Tuza, Maximum Cuts and Largest Bipartite Subgraphs, in: Combinatorial Optimization, eds. Cook, Lov\u00e1sz, Seymour, AMS, 1995, 181\u2013244.","DOI":"10.1090\/dimacs\/020\/04"},{"key":"36_CR28","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1090\/pspum\/019\/9959","volume":"19","author":"D. K. Ray-Chaudhuri","year":"1971","unstructured":"D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman's Schoolgirl Problem, Proc. Symp. Math. 19, 1971, 187\u2013203.","journal-title":"Proc. Symp. Math."},{"key":"36_CR29","first-page":"23","volume":"3","author":"V. G. Vizing","year":"1964","unstructured":"V. G. Vizing, On an Estimate of the Chromatic Class of a p-Graph, (in Russian), Diskret. Analiz 3, 1964, 23\u201330.","journal-title":"Diskret. Analiz"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:02:35Z","timestamp":1605628955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}