{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:22Z","timestamp":1744217542318,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662535356"},{"type":"electronic","value":"9783662535363"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53536-3_12","type":"book-chapter","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T12:39:25Z","timestamp":1474979965000},"page":"133-144","source":"Crossref","is-referenced-by-count":4,"title":["Tight Bounds for Gomory-Hu-like Cut Counting"],"prefix":"10.1007","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[]},{"given":"Lior","family":"Kamma","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"key":"12_CR1","volume-title":"Network Flows - Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications. Prentice Hall, Upper Saddle River (1993)"},{"issue":"3","key":"12_CR2","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0097539792236730","volume":"24","author":"AA Bencz\u00far","year":"1995","unstructured":"Bencz\u00far, A.A.: Counterexamples for directed and node capacitated cut-trees. SIAM J. Comput. 24(3), 505\u2013510 (1995)","journal-title":"SIAM J. Comput."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Hariharan, R., Kavitha, T., Panigrahi, D.: An $$\\tilde{O}(mn)$$ Gomory-Hu tree construction algorithm for unweighted graphs. In: STOC 2007, pp. 605\u2013614 (2007)","DOI":"10.1145\/1250790.1250879"},{"key":"12_CR4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s004539910003","volume":"26","author":"S Chaudhuri","year":"2000","unstructured":"Chaudhuri, S., Subrahmanyam, K.V., Wagner, F., Zaroliagis, C.D.: Computing mimicking networks. Algorithmica 26, 31\u201349 (2000)","journal-title":"Algorithmica"},{"issue":"3","key":"12_CR5","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02115755","volume":"33","author":"C Cheng","year":"1991","unstructured":"Cheng, C., Hu, T.: Ancestor tree for arbitrary multi-terminal cut functions. Ann. Oper. Res. 33(3), 199\u2013213 (1991)","journal-title":"Ann. Oper. Res."},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Kamma, L., Krauthgamer, R.: Tight bounds for Gomory-Hu-like cut counting. CoRR abs\/1511.08647 (2015)","DOI":"10.1007\/978-3-662-53536-3_12"},{"key":"12_CR7","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)"},{"issue":"3","key":"12_CR8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9, 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"12_CR10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0219009","volume":"19","author":"D Gusfield","year":"1990","unstructured":"Gusfield, D.: Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19(1), 143\u2013155 (1990)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"12_CR11","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":"1","key":"12_CR12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2005","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2005)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"12_CR13","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."},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Rika, I.: Mimicking networks and succinct representations of terminal cuts. In: SODA 2013, pp. 1789\u20131799. SIAM (2013)","DOI":"10.1137\/1.9781611973105.128"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53536-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T22:01:40Z","timestamp":1568412100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53536-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662535356","9783662535363"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53536-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}