{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:29:12Z","timestamp":1736573352393,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055806","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"562-570","source":"Crossref","is-referenced-by-count":11,"title":["Approximating maximum independent sets in uniform hypergraphs"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Hofmeister","sequence":"first","affiliation":[]},{"given":"Hanno","family":"Lefmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai and A. Itai, A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem, Journal of Algorithms 7, 1986, 567\u2013583.","journal-title":"Journal of Algorithms"},{"key":"53_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon and N. Kahale, Approximating the Independence Number via the \u03b8-Function, Mathematical Programming, to appear.","DOI":"10.1007\/BF01581168"},{"key":"53_CR3","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J. Spencer, The Probabilistic Method, Wiley & Sons, NY, 1992."},{"key":"53_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1997","unstructured":"A. Blum and D. Karger, An \u00d5(n 3\/14)-coloring Algorithm for 3-colorable Graphs, Information Processing Letters 61, 1997, 49\u201353.","journal-title":"Information Processing Letters"},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"R. Boppana and M. Halld\u00f3rsson, Approximating Maximum Independent Sets by Excluding Subgraphs, BIT 32, 1992, 180\u2013196, also in: Proc. 2nd Scandin. Workshop on Algorithm Theory (SWAT), Springer, LNCS 447, 1990, 13\u201325.","journal-title":"BIT"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0020-0190(92)90228-N","volume":"42","author":"E. Dahlhaus","year":"1992","unstructured":"E. Dahlhaus, M. Karpinski and P. Kelsen, An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3, Information Processing Letters 42, 1992, 309\u2013313.","journal-title":"Information Processing Letters"},{"key":"53_CR7","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1112\/plms\/s3-2.1.417","volume":"2","author":"P. Erd\u00f6s","year":"1952","unstructured":"P. Erd\u00f6s and R. Rado, Combinatorial Theorems on Classification of Subsets of a Given Set, Proceedings London Mathematical Society 2, 1952, 417\u2013439.","journal-title":"Proceedings London Mathematical Society"},{"key":"53_CR8","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, Zero Knowledge and the Chromatic Number, Proc. 11th IEEE Conference on Computational Complexity, 1996, 278\u2013287.","DOI":"10.1109\/CCC.1996.507690"},{"key":"53_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/0406036","volume":"6","author":"M. Goldberg","year":"1993","unstructured":"M. Goldberg and T. Spencer, An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size, SIAM Journal of Discrete Math. 6, 1993, 443\u2013459.","journal-title":"SIAM Journal of Discrete Math."},{"key":"53_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M. Halld\u00f3rsson","year":"1993","unstructured":"M. Halld\u00f3rsson, A Still Better Performance Guarantee for Approximate Graph Coloring, Information Processing Letters 45, 1993, 19\u201323.","journal-title":"Information Processing Letters"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"M. Halld\u00f3rsson and J. Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-degree Graphs, Proc. 26th ACM Symposium on the Theory of Computing (STOC), 1994, 439\u2013448.","DOI":"10.1145\/195058.195221"},{"key":"53_CR12","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is Hard to Approximate Within n 1-\u025b, Proc. 37th IEEE Symposium on Foundations of Computer Science (FOCS), 1996, 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"53_CR13","first-page":"513","volume":"X","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, Worst Case Behaviour of Graph Coloring Algorithms, Proc. 5th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium X, 1974, 513\u2013527.","journal-title":"Congressus Numerantium"},{"key":"53_CR14","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani and M. Sudan, Approximate Graph Coloring by Semidefinite Programming, Proc. 35th IEEE Symposium on Foundations of Computer Science (FOCS), 1994, 2\u201313.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"53_CR15","doi-asserted-by":"crossref","unstructured":"P. Kelsen, On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph, Proc. 24th ACM Symposium on the Theory of Computing (STOC), 1992, 339\u2013350.","DOI":"10.1145\/129712.129745"},{"key":"53_CR16","doi-asserted-by":"crossref","unstructured":"P. Kelsen, S. Mahajan and H. Ramesh, Approximate Hypergraph Coloring, Proc. 6th Scandin. Workshop on Algorithm Theory (SWAT), Springer, 1996, 41\u201352.","DOI":"10.1007\/3-540-61422-2_119"},{"key":"53_CR17","unstructured":"J. Ne\u0161et\u0159il, Ramsey Theory, in: Handbook of Combinatorics Vol II, eds. R. L. Graham, M. Gr\u00f6tschel and L. Lov\u00e1sz, North-Holland, 1995, 1331\u20131403."},{"key":"53_CR18","doi-asserted-by":"crossref","unstructured":"R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"53_CR19","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0012-365X(72)90084-2","volume":"2","author":"J. Spencer","year":"1972","unstructured":"J. Spencer, Tur\u00e1n's Theorem for k-Graphs, Discrete Math. 2, 1972, 183\u2013186.","journal-title":"Discrete Math."},{"key":"53_CR20","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"A. Wigderson, Improving the Performance Guarantee for Approximate Graph Coloring, Journal of the ACM 30, 1983, 729\u2013735.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T13:52:35Z","timestamp":1736517155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0055806","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}