{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:12Z","timestamp":1781078292274,"version":"3.54.1"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319517407","type":"print"},{"value":"9783319517414","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-51741-4_9","type":"book-chapter","created":{"date-parts":[[2017,1,6]],"date-time":"2017-01-06T08:06:46Z","timestamp":1483690006000},"page":"103-115","source":"Crossref","is-referenced-by-count":1,"title":["Vertex Sparsification in Trees"],"prefix":"10.1007","author":[{"given":"Gramoz","family":"Goranci","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harald","family":"R\u00e4cke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,1,7]]},"reference":[{"key":"9_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report, Tel Aviv University (1987)"},{"key":"9_CR2","unstructured":"Andersen, R., Feige, U.: Interchanging distance and capacity in probabilistic mappings. CoRR, arXiv:abs\/0907.3631 (2009)"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Gupta, A., Krauthgamer, R.: Towards (1+ $$\\varepsilon $$ )-approximate flow sparsifiers. In: Proceedings of the 25th SODA, pp. 279\u2013293 (2014)","DOI":"10.1137\/1.9781611973402.20"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t minimum cuts in \u00d5(n $${}^{\\text{2}}$$ ) time. In: Proceedings of the 28th STOC, pp. 47\u201355 (1996)","DOI":"10.1145\/237814.237827"},{"issue":"1","key":"9_CR5","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.20165","volume":"50","author":"C Chekuri","year":"2007","unstructured":"Chekuri, C., Shepherd, F.B., Oriolo, G., Scutell\u00e0, M.G.: Hardness of robust network design. Networks 50(1), 50\u201354 (2007)","journal-title":"Networks"},{"key":"9_CR6","unstructured":"Cheung, Y.K., Goranci, G., Henzinger, M.: Graph minors for preserving terminal distances approximately - lower and upper bounds. In: Proceedings of the 43rd ICALP, pp. 131:1\u2013131:14 (2016)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: On vertex sparsifiers with steiner nodes. In: Proceedings of the 44th STOC, pp. 673\u2013688 (2012)","DOI":"10.1145\/2213977.2214039"},{"key":"9_CR8","unstructured":"Gupta, A.: Steiner points in tree metrics don\u2019t (really) help. In: Proceedings of the 12th SODA, pp. 220\u2013227 (2001)"},{"issue":"3","key":"9_CR9","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1006\/jcss.1998.1592","volume":"57","author":"T Hagerup","year":"1998","unstructured":"Hagerup, T., Katajainen, J., Nishimura, N., Ragde, P.: Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci. 57(3), 366\u2013375 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9_CR10","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1137\/140951382","volume":"44","author":"L Kamma","year":"2015","unstructured":"Kamma, L., Krauthgamer, R., Nguyen, H.L.: Cutting corners cheaply, or how to remove steiner points. SIAM J. Comput. 44(4), 975\u2013995 (2015)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/j.ipl.2014.02.011","volume":"114","author":"A Khan","year":"2014","unstructured":"Khan, A., Raghavendra, P.: On mimicking networks representing minimum terminal cuts. Inf. Process. Lett. 114(7), 365\u2013371 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9_CR12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1137\/120888843","volume":"28","author":"R Krauthgamer","year":"2014","unstructured":"Krauthgamer, R., Nguyen, H.L., Zondiner, T.: Preserving terminal distances using minors. SIAM J. Discrete Math. 28(1), 127\u2013141 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Rika, I.: Mimicking networks and succinct representations of terminal cuts. In: Proceedings of the 24th SODA, pp. 1789\u20131799 (2013)","DOI":"10.1137\/1.9781611973105.128"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Leighton, F.T., Moitra, A.: Extensions and limits to vertex sparsification. In: Proceedings of the 42nd STOC, pp. 47\u201356 (2010)","DOI":"10.1145\/1806689.1806698"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Makarychev, Y.: Metric extension operators, vertex sparsifiers and lipschitz extendability. In: Proceedings of the 51th FOCS, pp. 255\u2013264 (2010)","DOI":"10.1109\/FOCS.2010.31"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proceedings of the 50th FOCS (2009)","DOI":"10.1109\/FOCS.2009.28"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th STOC, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H., Shah, C., T\u00e4ubig, H.: Computing cut-based hierarchical decompositions in almost linear time. In: Proceedings of the 25th SODA, pp. 227\u2013238 (2014)","DOI":"10.1137\/1.9781611973402.17"},{"issue":"4","key":"9_CR19","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51741-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T06:37:54Z","timestamp":1568702274000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51741-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319517407","9783319517414"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51741-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}