{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:13Z","timestamp":1759063573957,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_1","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"3-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Approximation of Centrality and Distances in Hyperbolic Graphs"],"prefix":"10.1007","author":[{"given":"V.","family":"Chepoi","sequence":"first","affiliation":[]},{"given":"F. F.","family":"Dragan","sequence":"additional","affiliation":[]},{"given":"M.","family":"Habib","sequence":"additional","affiliation":[]},{"given":"Y.","family":"Vax\u00e8s","sequence":"additional","affiliation":[]},{"given":"H.","family":"Alrasheed","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Wang, J., Vassilevska Williams, V.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: SODA (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Vassilevska Williams, V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: SODA, pp. 1681\u20131697 (2015)","DOI":"10.1137\/1.9781611973730.112"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/net.21631","volume":"67","author":"M Abu-Ata","year":"2016","unstructured":"Abu-Ata, M., Dragan, F.F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67, 49\u201368 (2016)","journal-title":"Networks"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (w\/o matrix multiplication). SIAM J. Comput. 28, 1167\u201381 (1999)","journal-title":"SIAM J. Comput."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/978-3-540-73951-7_47","volume-title":"Algorithms and Data Structures","author":"P Berman","year":"2007","unstructured":"Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 541\u2013552. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73951-7_47"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.entcs.2016.03.005","volume":"322","author":"M Borassi","year":"2016","unstructured":"Borassi, M., Crescenzi, P., Habib, M.: Into the square - on the complexity of quadratic-time solvable problems. Electron. Notes Theor. Comput. Sci. 322, 51\u201367 (2016)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82, 43\u201377 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.F.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms 30, 166\u2013184 (1999)","journal-title":"J. Algorithms"},{"key":"1_CR9","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-Positive Curvature","author":"Martin R. Bridson","year":"1999","unstructured":"Bridson, M.R., Haefiger, A.: Metric Spaces of Non-Positive Curvature, Grundlehren der Mathematischen Wissenschaften. vol. 319, Springer (1999). https:\/\/doi.org\/10.1007\/978-3-662-12494-9"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Chechik, S., Larkin, D., Roditty, L., Schoenebeck, G., Tarjan, R.E.: and Williams, V.V.: Better approximation algorithms for the graph diameter. In: SODA (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Chepoi, V., Dragan, F.F., Ducoffe, G., Mohammed, A., Vax\u00e8s, Y.: Fast approximation and exact computation of negative curvature parameters of graphs. In: SoCG (2018)","DOI":"10.1007\/s00454-019-00107-9"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BFb0049406","volume-title":"Algorithms \u2014 ESA \u201994","author":"V Chepoi","year":"1994","unstructured":"Chepoi, V., Dragan, F.: A linear-time algorithm for finding a central vertex of a chordal graph. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 159\u2013170. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0049406"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Chepoi, V.D., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: SoCG (2008)","DOI":"10.1145\/1377676.1377687"},{"key":"1_CR14","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 schemes for hyperbolic graphs. Algorithmica 62, 713\u2013732 (2012)","journal-title":"Algorithmica"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Habib, M., Vax\u00e8s, Y., Al-Rasheed, H.: Fast approximation of centrality and distances in hyperbolic graphs. arXiv:1805.07232 (2018)","DOI":"10.1007\/978-3-030-04651-4_1"},{"key":"1_CR16","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Center and diameter problems in plane triangulations and quadrangulations. In: SODA, pp. 346\u2013355 (2002)"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Core congestion is inherent in hyperbolic networks. In: SODA, pp. 2264\u20132279 (2017)","DOI":"10.1137\/1.9781611974782.149"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-540-74208-1_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","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.) APPROX\/RANDOM -2007. LNCS, vol. 4627, pp. 59\u201373. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74208-1_5"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.10098","volume":"42","author":"DG Corneil","year":"2003","unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E.: On the power of BFS to determine a graph\u2019s diameter. Networks 42, 209\u2013222 (2003)","journal-title":"Networks"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29, 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discr. Math. 307, 208\u2013229 (2007)","journal-title":"Discr. Math."},{"key":"1_CR22","unstructured":"Dragan, F.F.: Centers of graphs and the Helly property (in Russian), Ph.D. thesis, Moldova State University (1989)"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.09.002","volume":"57","author":"FF Dragan","year":"2005","unstructured":"Dragan, F.F.: Estimating all pairs shortest paths in restricted graph families: a unified approach. J. Algorithms 57, 1\u201321 (2005)","journal-title":"J. Algorithms"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.dam.2017.07.017","volume":"232","author":"FF Dragan","year":"2017","unstructured":"Dragan, F.F., K\u00f6hler, E., Alrasheed, H.: Eccentricity approximating trees. Discrete Appl. Math. 232, 142\u2013156 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-62559-3_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"FF Dragan","year":"1997","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: LexBFS-orderings and powers of graphs. In: d\u2019Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG 1996. LNCS, vol. 1197, pp. 166\u2013180. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-62559-3_15"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Edwards, K., Kennedy, W.S., Saniee, I.: Fast approximation algorithms for p-centres in large $$delta$$-hyperbolic graphs, CoRR, vol. abs\/1604.07359 (2016)","DOI":"10.1007\/978-3-319-49787-7_6"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Ghys, E., de la Harpe, P. (eds.) Les groupes hyperboliques d\u2019apr\u00e8s Gromov, M. Progress in Mathematics, Vol. 83 Birkh\u00e4user (1990)","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"1_CR28","series-title":"Mathematical Sciences Research Institute Publications","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3","volume-title":"Essays in Group Theory","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8. Springer, New York (1987). https:\/\/doi.org\/10.1007\/978-1-4613-9586-7_3"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1287\/opre.12.3.450","volume":"12","author":"SL Hakimi","year":"1964","unstructured":"Hakimi, S.L.: Optimum location of switching centers and absolute centers and medians of a graph. Oper. Res. 12, 450\u2013459 (1964)","journal-title":"Oper. Res."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1515\/crll.1869.70.185","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages des lignes. J. Reine Angew. Math. 70, 185\u2013190 (1869)","journal-title":"J. Reine Angew. Math."},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S0895480195295471","volume":"17","author":"D Kratsch","year":"2003","unstructured":"Kratsch, D., Le, H.-O., M\u00fcller, H., Prisner, E., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math. 17, 332\u2013340 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"1_CR33","doi-asserted-by":"publisher","first-page":"066108","DOI":"10.1103\/PhysRevE.84.066108","volume":"84","author":"O Narayan","year":"2011","unstructured":"Narayan, O., Saniee, I.: Large-scale curvature of networks. Phys. Rev. E 84(6), 066108 (2011)","journal-title":"Phys. Rev. E"},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BFb0023484","volume-title":"STACS 97","author":"E Prisner","year":"1997","unstructured":"Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 499\u2013510. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0023484"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0012-365X(00)00030-3","volume":"220","author":"E Prisner","year":"2000","unstructured":"Prisner, E.: Eccentricity-approximating trees in chordal graphs. Discr. Math. 220, 263\u2013269 (2000)","journal-title":"Discr. Math."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: STOC, pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1109\/TNET.2007.899021","volume":"16","author":"Y Shavitt","year":"2008","unstructured":"Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE\/ACM Trans. Netw. 16, 25\u201336 (2008)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Verbeek, K., Suri, S.: Metric embedding, hyperbolic space, and social networks. In: SoCG, pp. 501\u2013510 (2014)","DOI":"10.1145\/2582112.2582139"},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1227\u20131237. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_101"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:46:20Z","timestamp":1710344780000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}