{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:34:02Z","timestamp":1725514442307},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_50","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T07:36:39Z","timestamp":1185089799000},"page":"554-565","source":"Crossref","is-referenced-by-count":1,"title":["Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces"],"prefix":"10.1007","author":[{"given":"Yingchao","family":"Zhao","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"50_CR1","doi-asserted-by":"crossref","unstructured":"Barnes, E.R., Hoffman, A.J.: Partitioning, spectra and linear programming. In: Progress in Combinatorial Optimization, pp. 13\u201325 (1984)","DOI":"10.1016\/B978-0-12-566780-7.50007-6"},{"key":"50_CR2","volume-title":"SVD and Signal Processing: Algorithms","author":"P. Dewilde","year":"1988","unstructured":"Dewilde, P., Deprettere, E.F.: Singular value decomposition: An introduction. In: Deprettere, E.F. (ed.) SVD and Signal Processing: Algorithms, Elsevier Science Publishers, Amsterdam (1988)"},{"key":"50_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF02288367","volume":"1","author":"C. Eckart","year":"1936","unstructured":"Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika\u00a01, 211\u2013218 (1936)","journal-title":"Psychometrika"},{"key":"50_CR4","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1090\/S0002-9904-1939-06910-3","volume":"45","author":"C. Eckart","year":"1939","unstructured":"Eckart, C., Young, G.: A principal axis transformation for non-Hermitian matrices. Bulletin of the American Mathematical Society\u00a045, 118\u2013121 (1939)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"50_CR5","doi-asserted-by":"crossref","unstructured":"Feder, T., et al.: Complexity of Graph Partition Problems. In: STOC, 1999, pp. 464\u2013472 (1999)","DOI":"10.1145\/301250.301373"},{"issue":"98","key":"50_CR6","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"Fiedler, M.: Algebraic connectivity of graphs. Czechoslovak Mathematical Journal\u00a023(98), 298\u2013305 (1973)","journal-title":"Czechoslovak Mathematical Journal"},{"key":"50_CR7","first-page":"16","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1992","unstructured":"Golub, G.H., Van Loan, G.F.: Matrix Computations, pp. 16\u201321. Johns Hopkins University Press, Baltimore (1992)"},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: STOC, 2002, pp. 741\u2013750 (2002)","DOI":"10.1145\/509907.510013"},{"key":"50_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"50_CR10","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09, 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"50_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., et al.: Separators for sphere-packings and nearest neighbor graphs. J. ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"50_CR12","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl.\u00a011, 430\u2013452 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"50_CR13","first-page":"462","volume-title":"Proceedings at the 5th Symposium Discrete Algorithms","author":"S. Plotkin","year":"1994","unstructured":"Plotkin, S., Rao, S., Smith, W.D.: Shallow excluded minors and improved graph decomposition. In: Proceedings at the 5th Symposium Discrete Algorithms, pp. 462\u2013470. SIAM, New York (1994)"},{"key":"50_CR14","doi-asserted-by":"publisher","first-page":"3413","DOI":"10.1090\/S0002-9939-01-05931-7","volume":"129","author":"M. Ruzhansky","year":"2001","unstructured":"Ruzhansky, M.: On uniform properties of doubling measures. Proc. of Amer. Math. Soc.\u00a0129, 3413\u20133416 (2001)","journal-title":"Proc. of Amer. Math. Soc."},{"key":"50_CR15","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF01449770","volume":"63","author":"E. Schmidt","year":"1907","unstructured":"Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willk\u00fcrlichen Funktionen nach System vorgeschriebener. Mathematische Annalen\u00a063, 433\u2013476 (1907)","journal-title":"Mathematische Annalen"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: STOC, 2004, pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"50_CR17","unstructured":"Speilman, D.A., Teng, S.-H.: Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. In: FOCS, 1996, pp. 96\u2013105 (1996)"},{"key":"50_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0925-7721(96)00008-9","volume":"9","author":"S.-H. Teng","year":"1998","unstructured":"Teng, S.-H.: Combinatorial aspects of geometric graphs. Computational Geometry\u00a09, 277\u2013287 (1998)","journal-title":"Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T03:29:41Z","timestamp":1629430181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_50","relation":{},"subject":[]}}