{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:27:59Z","timestamp":1778495279226,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,17]],"date-time":"2017-02-17T00:00:00Z","timestamp":1487289600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,2,17]],"date-time":"2017-02-17T00:00:00Z","timestamp":1487289600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1160995"],"award-info":[{"award-number":["IIS-1160995"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-017-0291-7","type":"journal-article","created":{"date-parts":[[2017,2,17]],"date-time":"2017-02-17T15:11:30Z","timestamp":1487344290000},"page":"772-800","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5614-5477","authenticated-orcid":false,"given":"Bhaskar","family":"Das Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nasim","family":"Mobasheri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farzane","family":"Yahyanejad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,17]]},"reference":[{"issue":"3","key":"291_CR1","doi-asserted-by":"publisher","first-page":"032811","DOI":"10.1103\/PhysRevE.89.032811","volume":"89","author":"R Albert","year":"2014","unstructured":"Albert, R., DasGupta, B., Mobasheri, N.: Topological implications of negative curvature for biological and social networks. Phys. Rev. E 89(3), 032811 (2014)","journal-title":"Phys. Rev. E"},{"key":"291_CR2","doi-asserted-by":"crossref","unstructured":"Ariaei, F., Lou, M., Jonckheere, E., Krishnamachari, B., Zuniga, M.: Curvature of sensor network: clustering coefficient. EURASIP J. Wirel. Commun. Netw. 2008, 213185 (2009)","DOI":"10.1155\/2008\/213185"},{"key":"291_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"key":"291_CR4","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1007\/s00453-014-9927-z","volume":"70","author":"S Assadi","year":"2014","unstructured":"Assadi, S., Emamjomeh-Zadeh, E., Norouzi-Fard, A., Yazdanbod, S., Zarrabi-Zadeh, H.: The minimum vulnerability problem. Algorithmica 70, 718\u2013731 (2014)","journal-title":"Algorithmica"},{"key":"291_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min\u2013max graph partitioning and small set expansion. In: 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201326 (2011)","DOI":"10.1109\/FOCS.2011.79"},{"key":"291_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02783040","volume":"108","author":"I Benjamini","year":"1998","unstructured":"Benjamini, I.: Expanders are not hyperbolic. Isr. J. Math. 108, 33\u201336 (1998)","journal-title":"Isr. J. Math."},{"key":"291_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/jgt.20496","volume":"66","author":"I Benjamini","year":"2011","unstructured":"Benjamini, I., Hoppen, C., Ofek, E., Pralat, P., Wormald, N.: Geodesics and almost geodesic cycles in random regular graphs. J. Graph Theory 66, 115\u2013136 (2011)","journal-title":"J. Graph Theory"},{"key":"291_CR8","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O.: Finite transitive graph embedding into a hyperbolic metric space must stretch or squeeze. In: Klartag, B., Mendelson, S., Milman V.D. (eds.) Geometric Aspects of Functional Analysis, pp. 123\u2013126. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-29849-3_5"},{"key":"291_CR9","first-page":"105","volume-title":"Lecture Notes in Computer Science","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) Lecture Notes in Computer Science, vol. 317, pp. 105\u2013118. Springer, Berlin (1988)"},{"key":"291_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-positive Curvature","author":"MR Bridson","year":"1999","unstructured":"Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Springer, Berlin (1999)"},{"key":"291_CR11","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual Symposium on Computational Geometry, pp. 59\u201368 (2008)","DOI":"10.1145\/1377676.1377687"},{"issue":"3\u20134","key":"291_CR12","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V Chepoi","year":"2012","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for $$\\delta $$-hyperbolic graphs. Algorithmica 62(3\u20134), 713\u2013732 (2012)","journal-title":"Algorithmica"},{"key":"291_CR13","first-page":"59","volume-title":"Lecture Notes in Computer Science","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B.: Packing and covering $$\\delta $$-hyperbolic spaces by balls. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) Lecture Notes in Computer Science, vol. 4627, pp. 59\u201373. Springer, Berlin (2007)"},{"key":"291_CR14","doi-asserted-by":"crossref","unstructured":"Chung, F.R.K.: Spectral graph theory. In: CBMS Regional Conference Series in Mathematics, vol. 92 (1997)","DOI":"10.1090\/cbms\/092"},{"key":"291_CR15","doi-asserted-by":"crossref","unstructured":"de Montgolfier, F., Soto, M., Viennot, L.:. Treewidth and hyperbolicity of the internet. In: Proceedings of the 10th IEEE International Symposium on Networking Computing and Applications, pp. 25\u201332 (2011)","DOI":"10.1109\/NCA.2011.11"},{"issue":"11","key":"291_CR16","doi-asserted-by":"publisher","first-page":"1571","DOI":"10.1109\/TC.2010.257","volume":"60","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Goodrich, M.T.: Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Comput. 60(11), 1571\u20131580 (2011)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"291_CR17","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/1077464.1077470","volume":"1","author":"G Even","year":"2005","unstructured":"Even, G., Kortsarz, G., Slany, W.: On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans. Algorithms 1(1), 74\u2013101 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"6\u20138","key":"291_CR18","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.ipl.2015.02.002","volume":"115","author":"H Fournier","year":"2015","unstructured":"Fournier, H., Ismail, A., Vigneron, A.: Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett. 115(6\u20138), 576\u2013579 (2015)","journal-title":"Inf. Process. Lett."},{"key":"291_CR19","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.dam.2015.05.028","volume":"194","author":"R Gandhi","year":"2015","unstructured":"Gandhi, R., Kortsarz, G.: On edge expansion problems and the small set expansion conjecture. Discr. Appl. Math. 194, 93\u2013101 (2015)","journal-title":"Discr. Appl. Math."},{"key":"291_CR20","first-page":"1071","volume-title":"Lecture Notes in Computer Science","author":"C Gavoille","year":"2005","unstructured":"Gavoille, C., Ly, O.: Distance labeling in hyperbolic graphs. In: Deng, X., Du, D.-Z. (eds.) Lecture Notes in Computer Science, vol. 3827, pp. 1071\u20131079. Springer, Berlin (2005)"},{"key":"291_CR21","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory, pp. 75\u2013263. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"2","key":"291_CR22","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.20275","volume":"57","author":"E Jonckheere","year":"2007","unstructured":"Jonckheere, E., Lohsoonthorn, P., Bonahon, F.: Scaled Gromov hyperbolic graphs. J. Graph Theory 57(2), 157\u2013180 (2007)","journal-title":"J. Graph Theory"},{"issue":"3","key":"291_CR23","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1080\/15427951.2011.601233","volume":"7","author":"E Jonckheere","year":"2011","unstructured":"Jonckheere, E., Lohsoonthorn, P., Ariaei, F.: Scaled Gromov four-point condition for network graph curvature computation. Internet Math. 7(3), 137\u2013177 (2011)","journal-title":"Internet Math."},{"issue":"1","key":"291_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/15427951.2010.554320","volume":"7","author":"E Jonckheere","year":"2011","unstructured":"Jonckheere, E., Lou, M., Bonahon, F., Baryshnikov, Y.: Euclidean versus hyperbolic congestion in idealized versus experimental networks. Internet Math. 7(1), 1\u201327 (2011)","journal-title":"Internet Math."},{"key":"291_CR25","doi-asserted-by":"crossref","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: 26th IEEE International Conference on Computer Communications, pp. 1902\u20131909 (2007)","DOI":"10.1109\/INFCOM.2007.221"},{"key":"291_CR26","doi-asserted-by":"crossref","unstructured":"Louis, A., Raghavendra, P., Vempala, S.: The complexity of approximating vertex expansion. In: 54th IEEE Annual Symposium on Foundations of Computer Science, vol. 360\u2013369 (2013)","DOI":"10.1109\/FOCS.2013.46"},{"key":"291_CR27","unstructured":"Malyshev, A.: Expanders are order diameter non-hyperbolic. \n                    arXiv:1501.07904\n                    \n                   (2015)"},{"issue":"3","key":"291_CR28","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1080\/15427951.2014.1002640","volume":"11","author":"O Narayan","year":"2015","unstructured":"Narayan, O., Saniee, I., Tucci, G.H.: Lack of hyperbolicity in asymptotic Erd\u00f6s\u2013Renyi sparse random graphs. Internet Math. 11(3), 277\u2013288 (2015)","journal-title":"Internet Math."},{"issue":"4","key":"291_CR29","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s10878-012-9462-2","volume":"26","author":"MT Omran","year":"2013","unstructured":"Omran, M.T., Sack, J.-R., Zarrabi-Zadeh, H.: Finding paths with minimum shared edges. J. Comb. Optim. 26(4), 709\u2013722 (2013)","journal-title":"J. Comb. Optim."},{"key":"291_CR30","doi-asserted-by":"crossref","unstructured":"Papadopoulos, F., Krioukov, D., Boguna, M., Vahdat, A.: Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: IEEE INFOCOM, pp. 1\u20139 (2010)","DOI":"10.1109\/INFCOM.2010.5462131"},{"key":"291_CR31","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: 45th ACM Symposium on Theory of Computing, pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"291_CR32","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tetali, P.: Approximations for the isoperimetric and spectral profile of graphs and related parameters. In: 45th ACM Symposium on Theory of Computing, pp. 631\u2013640 (2010)","DOI":"10.1145\/1806689.1806776"},{"key":"291_CR33","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: IEEE Conference on Computational Complexity, pp. 64\u201373 (2012)","DOI":"10.1109\/CCC.2012.43"},{"issue":"1","key":"291_CR34","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"291_CR35","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"issue":"9","key":"291_CR36","doi-asserted-by":"publisher","first-page":"1130","DOI":"10.1109\/TC.2006.144","volume":"55","author":"J Wang","year":"2006","unstructured":"Wang, J., Yang, M., Yang, B., Zheng, S.Q.: Dual-homing based scalable partial multicast protection. IEEE Trans. Comput. 55(9), 1130\u20131141 (2006)","journal-title":"IEEE Trans. Comput."},{"key":"291_CR37","unstructured":"Yang, B., Yang, M., Wang, J., Zheng, S.Q.: Minimum cost paths subject to minimum vulnerability for reliable communications. In: 8th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 334\u2013339 (2005)"},{"issue":"5","key":"291_CR38","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1109\/TNET.2010.2044514","volume":"18","author":"SQ Zheng","year":"2010","unstructured":"Zheng, S.Q., Wang, J., Yang, B., Yang, M.: Minimum-cost multiple paths subject to minimum link and node sharing in a network. IEEE\/ACM Trans. Netw. 18(5), 1436\u20131449 (2010)","journal-title":"IEEE\/ACM Trans. Netw."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0291-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0291-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0291-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:25:11Z","timestamp":1589696711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0291-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,17]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["291"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0291-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,17]]},"assertion":[{"value":"13 March 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}