{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:30:19Z","timestamp":1725579019733},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_14","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T08:03:12Z","timestamp":1300089792000},"page":"125-135","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity Status of Problems Related to Sparsest Cuts"],"prefix":"10.1007","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[]},{"given":"Hajo","family":"Broersma","sequence":"additional","affiliation":[]},{"given":"Viresh","family":"Patel","sequence":"additional","affiliation":[]},{"given":"Artem","family":"Pyatkin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D. Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Journal of Machine Learning\u00a075, 245\u2013248 (2009)","journal-title":"Journal of Machine Learning"},{"key":"14_CR2","unstructured":"Aloise, D., Hansen, P.: On the complexity of minimum sum-of-squares clustering. Cahiers du GERAD, G\u20132007\u201350 (2007), \n                  \n                    http:\/\/www.gerad.ca"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. In: FOCS, pp. 329\u2013337 (2007)","DOI":"10.1109\/FOCS.2007.4389504"},{"issue":"5","key":"14_CR4","doi-asserted-by":"publisher","first-page":"1748","DOI":"10.1137\/080731049","volume":"39","author":"S. Arora","year":"2010","unstructured":"Arora, S., Hazan, E., Kale, S.: \n                  \n                    \n                  \n                  $O(\\sqrt{\\log n})$\n                 Approximation to SPARSEST CUT in \n                  \n                    \n                  \n                  $\\tilde{O}(n^2)$\n                 Time. SIAM J. Comput.\u00a039(5), 1748\u20131771 (2010)","journal-title":"SIAM J. Comput."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. In: STOC, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L.: Treewidth: algorithmic techniques and results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 19\u201336. Springer, Heidelberg (1997)"},{"issue":"2-3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0166-218X(03)00439-6","volume":"136","author":"P. Bonsma","year":"2004","unstructured":"Bonsma, P.: Sparsest cuts and concurrent flows in product graphs. Discrete Applied Mathematics\u00a0136(2-3), 173\u2013182 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Bonsma, P.: Linear time algorithms for finding sparsest cuts in various graph classes. In: CS 2006, Prague. Electronic Notes in Discrete Mathematics, vol.\u00a028, pp. 265\u2013272 (2007)","DOI":"10.1016\/j.endm.2007.01.039"},{"key":"14_CR10","unstructured":"Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cuts in graphs of bounded treewidth. arXiv:1006.3970v2 [cs.Ds] (June 23, 2010)"},{"key":"14_CR11","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","volume":"56","author":"P. Drineas","year":"2004","unstructured":"Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Journal of Machine Learning\u00a056, 9\u201333 (2004)","journal-title":"Journal of Machine Learning"},{"key":"14_CR13","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some Simplified NP-Complete Graph Problems. Theoretical Computer Science\u00a01, 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"14_CR15","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","volume":"27","author":"D.W. Matula","year":"1990","unstructured":"Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics\u00a027, 113\u2013123 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR17","unstructured":"Moret, B., Shapiro, H.: Algorithms from P to NP. Benjamin\/Cummings (1990)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T11:23:58Z","timestamp":1558437838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}