{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T12:48:08Z","timestamp":1759495688055,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642756"},{"type":"electronic","value":"9783540697152"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054322","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T05:37:37Z","timestamp":1149658657000},"page":"206-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Spectral techniques in graph algorithms"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,25]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"N. Alon, Eigenvalues and expanders, Combinatorial 6 (1986), 83\u201396.","journal-title":"Combinatorial"},{"key":"18_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica 7 (1987), 1\u201322.","journal-title":"Combinatorica"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon and N. Kahale, A spectral technique for coloring random 3-colorable graphs, Proc. of the 26th ACM STOC, ACM Press (1994), 346\u2013355. Also; SIAM J. Comput., in press.","DOI":"10.1145\/195058.195187"},{"key":"18_CR4","unstructured":"N. Alon and N. Kahale, Approximating the independence number via the \u03b8-function, Math. Programming, in press."},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Proc. of the Ninth Annual ACM-SIAM SODA, ACM Press (1998), to appear.","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"18_CR6","first-page":"320","volume-title":"Eigenvalues, expanders and superconcentrators","author":"N. Alon","year":"1984","unstructured":"N. Alon and V. D. Milman, Eigenvalues, expanders and superconcentrators, Proc. 25 th Annual Symp. on Foundations of Computer Science, Singer Island, Florida, IEEE (1984), 320\u2013322. (Also: \u03bb1, isoperimetric inequalities for graphs and superconcentrators, J. Combinatorial Theory, Ser. B 38 (1985), 73\u201388.)"},{"key":"18_CR7","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, New York, 1992."},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and intractability of approximation problems, Proc. of the 33rd IEEE FOCS, IEEE (1992), 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra, Probabilistic checking of proofs; a new characterization of NP, Proc. of the 33rd IEEE FOCS, IEEE (1992), 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"R. Boppana and M. M. Halld\u00f3rsson, Approximating maximum independent sets by excluding subgraphs, BIT, 32 (1992),180\u2013196.","journal-title":"BIT"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"A. Blum, Some tools for approximate 3-coloring, Proc. 31st IEEE FOCS, IEEE (1990), 554\u2013562.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"T.N. Bui","year":"1992","unstructured":"T.N. Bui and C. Jones, Finding good approximate vertex and edge partitions is NP-hard, Infor. Proc. Letters 42 (1992), 153\u2013159.","journal-title":"Infor. Proc. Letters"},{"key":"18_CR13","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 ~O(n3\/14)-colormg algorithm for 3-colorable graphs, IPL 61 (1997), 49\u201353.","journal-title":"IPL"},{"key":"18_CR14","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs, Academic Press, London, 1985."},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A. Blum","year":"1995","unstructured":"A. Blum and J. H. Spencer, Coloring random and semi-random k-colorable graphs, Journal of Algorithms 19 (1995), 204\u2013234.","journal-title":"Journal of Algorithms"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"R. Boppana, Eigenvalues and graph bisection: An average case analysis, Proc. 28th IEEE FOCS, IEEE (1987), 280\u2013285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"18_CR17","unstructured":"F. Chung and S. T. Yau, Eigenvalues, flows and separators of graphs, to appear."},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. E. Dyer","year":"1989","unstructured":"M. E. Dyer and A. M. Frieze, The solution of some random NP-Hard problems in polynomial expected time, Journal of Algorithms 10 (1989), 451\u2013489.","journal-title":"Journal of Algorithms"},{"key":"18_CR19","first-page":"420","volume":"17","author":"W. E. Donath","year":"1973","unstructured":"W. E. Donath and A. J. Hoffman, Lower bounds for the partitioning of graphs, J. Res. Develop. 17 (1973), 420\u2013425.","journal-title":"J. Res. Develop."},{"key":"18_CR20","first-page":"17","volume":"5","author":"P. Erd\u00f3s","year":"1960","unstructured":"P. Erd\u00f3s and A. R\u00e9nyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17\u201361.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"issue":"98","key":"18_CR21","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), 298\u2013305.","journal-title":"Czechoslovak Math. J."},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra and M. Szegedy, Approximating Clique is almost NP-complete, Proc. of the 32nd IEEE FOCS, IEEE (1991), 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"18_CR23","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"Z. F\u00fcredi and J. Koml\u00f3s, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), 233\u2013241.","journal-title":"Combinatorica"},{"key":"18_CR24","unstructured":"U. Feige and J. Kilian, Zero knowledge and the chromatic number, Proc. 11th Annual IEEE Conf. on Computational Complexity, 1996."},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"J. Friedman, J. Kahn and E. Szemer\u00e9di, On the second eigenvalue in random regular graphs, Proc. 21st ACM STOC, ACM Press (1989), 587\u2013598.","DOI":"10.1145\/73007.73063"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"A. Frieze and C. McDiarmid, Algorithmic theory of random graphs, Random Structures and Algorithms 10 (1997), 5\u201342.","journal-title":"Random Structures and Algorithms"},{"key":"18_CR27","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman and Company, 1979."},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is hard to approximate within n 1\u2212\u2203, Proc. 37th IEEE FOCS, IEEE (1996), 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"18_CR29","first-page":"79","volume-title":"Graph Theory and its Applications","author":"A. J. Hoffman","year":"1970","unstructured":"A. J. Hoffman, On eigenvalues and colorings of graphs, in: B. Harris Ed., Graph Theory and its Applications, Academic, New York and London, 1970, 79\u201391."},{"key":"18_CR30","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M. Jerrum","year":"1992","unstructured":"M. Jerrum, Large cliques elude the metropolis process, Random Structures and Algorithms 3 (1992), 347\u2013359.","journal-title":"Random Structures and Algorithms"},{"key":"18_CR31","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, In: Complexity of computer computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York, 1972, pp. 85\u2013103."},{"key":"18_CR32","first-page":"1","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"R. M. Karp","year":"1976","unstructured":"R. M. Karp, Probabilistic analysis of some combinatorial search problems, In: Algorithms and Complexity: New Directions and Recent Results, J. F. Traub, ed., Academic Press, New York, 1976, pp. 1\u201319."},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"L. Ku\u010dera, Expected behavior of graph colouring algorithms, In Lecture Notes in Computer Science No. 56, Springer-Verlag, 1977, pp. 447\u2013451.","DOI":"10.1007\/3-540-08442-8_114"},{"key":"18_CR34","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L. Ku\u010dera","year":"1995","unstructured":"L. Ku\u010dera, Expected complexity of graph partitioning problems, Discrete Applied Math. 57 (1995), 193\u2013212.","journal-title":"Discrete Applied Math."},{"key":"18_CR35","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semi-definite programming, In 35th Symposium on Foundations of Computer Science, pages 2\u201313. IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"18_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory IT-25, (1979), 1\u20137.","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR37","volume-title":"Combinatorial Problems and Exercises","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Chapter 11."},{"key":"18_CR38","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, Proc 29th annual FOCS (1988), 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"18_CR39","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36(1979), 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"18_CR40","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. Proc. 25th ACM STOC (1993), 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"18_CR41","unstructured":"D. W. Matula, On the complete subgraph of a random graph, Combinatory Mathematics and its Applications, Chapel Hill, North Carolina (1970), 356\u2013369."},{"key":"18_CR42","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothem","year":"1990","unstructured":"A. Pothem, H. D. Simon and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl. 11 (1990), 430\u2013452.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"18_CR43","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(89)90214-8","volume":"74","author":"A. D. Petford","year":"1989","unstructured":"A. D. Petford and D. J. A. Welsh, A randomised 3-colouring algorithm, Discrete Mathematics, 74 (1989), 253\u2013261.","journal-title":"Discrete Mathematics"},{"key":"18_CR44","unstructured":"A. Ralston, A First Course in Numericad Analysis, McGraw-Hill, 1985, Section 10.4."},{"key":"18_CR45","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Dokl. Ak. Nauk. SSSR 281 (1985), 798\u2013801 (in Russian). English translation in: Sov. Math. Dokl. 31 (1985), 354\u2013357.","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"18_CR46","unstructured":"M. Saks, Private communication."},{"issue":"2\/3","key":"18_CR47","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0956-0521(91)90014-V","volume":"2","author":"H. D. Simon","year":"1991","unstructured":"H. D. Simon, Partitioning of unstructured problems for parallel processing, Computing Systmes in Engineering 2(2\/3) (1991), 135\u2013148.","journal-title":"Computing Systmes in Engineering"},{"key":"18_CR48","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A. Sinclair","year":"1989","unstructured":"A. Sinclair and M. R. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation 82 (1989), 93\u2013133.","journal-title":"Information and Computation"},{"key":"18_CR49","unstructured":"D. A. Spielman and S.-H. Teng, Spectral partitioning works: planar graphs and finite element meshes, to appear."},{"key":"18_CR50","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0196-6774(88)90005-3","volume":"9","author":"J. S. Turner","year":"1988","unstructured":"J. S. Turner, Almost all k-colorable graphs are easy to color, Journal of Algorithms 9 (1988), 63\u201382.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","LATIN'98: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:12:52Z","timestamp":1736406772000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054322"}},"subtitle":["Invited paper"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642756","9783540697152"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/bfb0054322","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"25 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}