{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:27:44Z","timestamp":1778495264170,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540742074","type":"print"},{"value":"9783540742081","type":"electronic"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"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":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_5","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T10:52:26Z","timestamp":1188211946000},"page":"59-73","source":"Crossref","is-referenced-by-count":29,"title":["Packing and Covering \u03b4-Hyperbolic Spaces by Balls"],"prefix":"10.1007","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertrand","family":"Estellon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/PL00009349","volume":"19","author":"N. Alon","year":"1998","unstructured":"Alon, N.: Piercing d-intervals. Discrete and Computational Geometry\u00a019, 333\u2013334 (1998)","journal-title":"Discrete and Computational Geometry"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0012-365X(02)00427-2","volume":"257","author":"N. Alon","year":"2002","unstructured":"Alon, N.: Covering a hypergraph of subgraphs. Discrete Mathematics\u00a0257, 249\u2013254 (2002)","journal-title":"Discrete Mathematics"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Moshkovitz, D., Safra, M.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms (to appear)","DOI":"10.1145\/1150334.1150336"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y","volume":"35","author":"N. Alon","year":"2000","unstructured":"Alon, N., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: Decreasing the diameter of bounded degree graphs. J. Graph Theory\u00a035, 161\u2013172 (2000)","journal-title":"J. Graph Theory"},{"key":"5_CR5","unstructured":"Alonso, J.M., Brady, T., Cooper, D., Ferlini, V., Lustig, M., Mihalik, M., Shapiro, M., Short, H.: Notes on word hyperbolic groups. In Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990. In: Ghys, E., Haefliger, A., Verjovsky, A. (eds.), World Scientific, pp. 3\u201363 (1991)"},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/S0895480100380902","volume":"16","author":"H.-J. Bandelt","year":"2003","unstructured":"Bandelt, H.-J., Chepoi, V.: 1-Hyperbolic graphs. SIAM J. Discrete Mathematics\u00a016, 323\u2013334 (2003)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Halldorsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM Journal on Computing 36, 1\u201315 (2006) (and SODA 2002)","DOI":"10.1137\/S0097539703437843"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02579383","volume":"6","author":"I. B\u00e1r\u00e1ny","year":"1986","unstructured":"B\u00e1r\u00e1ny, I., Edmonds, J., Wolsey, L.A.: Packing and covering a tree by subtrees. Combinatorica\u00a06, 221\u2013233 (1986)","journal-title":"Combinatorica"},{"key":"5_CR9","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North-Holland, Amsterdam (1989)"},{"key":"5_CR10","unstructured":"Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 296\u2013345. PWS, Boston, MA (1997)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1137\/S0895480194267853","volume":"10","author":"A. Brandst\u00e4dt","year":"1997","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: Clique r-domination and clique r-packing problems on dually chordal graphs. SIAM J. Discrete Mathematics\u00a010, 109\u2013127 (1997)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"5_CR12","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.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms\u00a030, 166\u2013184 (1999) (and ESA 1997)","journal-title":"J. Algorithms"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1287\/moor.6.1.50","volume":"6","author":"R. Chandrasekaran","year":"1981","unstructured":"Chandrasekaran, R., Doughety, A.: Location on tree networks: p-center and q-dispersion problems. Mathematics Operations Research\u00a06, 50\u201357 (1981)","journal-title":"Mathematics Operations Research"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(88)90120-5","volume":"22","author":"G.J. Chang","year":"1989","unstructured":"Chang, G.J.: Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics\u00a022, 21\u201334 (1988\/1989)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/0605034","volume":"5","author":"G.J. Chang","year":"1986","unstructured":"Chang, G.J., Nemhauser, G.L.: The k-domination and k-stability problems on sun-free chordal graphs. SIAM J. Alg. Disc. Meth.\u00a05, 332\u2013345 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"Chepoi, V., Dragan, F.: A note on distance approximating trees in graphs. European J. Combinatorics\u00a021, 761\u2013766 (2000)","journal-title":"European J. Combinatorics"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00454-006-1260-0","volume":"37","author":"V. Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B., Vax\u00e8s, Y.: On covering planar graphs with a fixed number of balls. Discrete and Computational Geometry\u00a037, 237\u2013244 (2007)","journal-title":"Discrete and Computational Geometry"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s00453-005-1183-9","volume":"45","author":"V. Chepoi","year":"2006","unstructured":"Chepoi, V., Estellon, B., Nouioua, K., Vax\u00e8s, Y.: Mixed covering of trees and the augmentation problem with odd diameter constraints. Algorithmica\u00a045, 209\u2013226 (2006)","journal-title":"Algorithmica"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00453-001-0113-8","volume":"33","author":"V. Chepoi","year":"2002","unstructured":"Chepoi, V., Vax\u00e8s, Y.: Augmenting trees to meet biconnectivity and diameter constraints. Algorithmica\u00a033, 243\u2013262 (2002)","journal-title":"Algorithmica"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1002\/jgt.3190080408","volume":"8","author":"F.R.K. Chung","year":"1984","unstructured":"Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. J. Graph Theory\u00a08, 511\u2013534 (1984)","journal-title":"J. Graph Theory"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-45061-0_3","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2003","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 33\u201347. Springer, Heidelberg (2003)"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: Proc. 31th Annual ACM Symposium on the Theory of Computing STOC 1999, pp. 750\u2013759 (1999)","DOI":"10.1145\/301250.301447"},{"key":"5_CR23","volume-title":"SODA 2007","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D.: Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. In: SODA 2007. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, ACM Press, New York (2007)"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s004930050035","volume":"18","author":"P. Erd\u00f6s","year":"1998","unstructured":"Erd\u00f6s, P., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: How to decrease the diameter of triangle\u2013free graphs. Combinatorica\u00a018, 493\u2013501 (1998)","journal-title":"Combinatorica"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M. Farber","year":"1984","unstructured":"Farber, M.: Domination, independent domination and duality in strongly chordal graphs. Discrete Applied Mathematics\u00a07, 115\u2013130 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proc. 20th ACM Symp. Theory of Computing, STOC 1988, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1007\/11602613_106","volume-title":"Algorithms and Computation","author":"C. Gavoille","year":"2005","unstructured":"Gavoille, C., Ly, O.: Distance labeling in hyperbolic graphs. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 1071\u20131079. Springer, Heidelberg (2005)"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Ghys, E., de la Harpe, P. (eds.:) Les groupes hyperboliques d\u2019apr\u00e8s M. Gromov. Progress in Mathematics vol. 83 Birkh\u00e4user (1990)","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic Groups. In: Gersten, S.M.( ed.) Essays in group theory, MSRI Series 8, pp. 75\u2013263 (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"5_CR30","unstructured":"Hochbaum, D.S.: Various notions of approximations: good, better, best, and more. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 346\u2013398. PWS, Boston MA (1997)"},{"key":"5_CR31","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D.S. Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM\u00a033, 533\u2013550 (1986)","journal-title":"Journal of the ACM"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.disopt.2005.10.006","volume":"3","author":"T. Ishii","year":"2006","unstructured":"Ishii, T., Yamamoto, S., Nagamochi, H.: Augmenting forests to meet odd diameter requirements. Discrete Optimization\u00a03, 154\u2013164 (2006)","journal-title":"Discrete Optimization"},{"key":"5_CR33","volume-title":"INFOCOM 2007","author":"R. Kleinberg","year":"2007","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: INFOCOM 2007. Proc. 26th Annual IEEE International Conference on Computer Communications, IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1006\/eujc.2002.0591","volume":"23","author":"J. Koolen","year":"2002","unstructured":"Koolen, J., Moulton, V.: Hyperbolic bridged graphs. European J. Combinatorics\u00a023, 683\u2013699 (2002)","journal-title":"European J. Combinatorics"},{"key":"5_CR35","volume-title":"FOCS 2006","author":"R. Krauthgamer","year":"2006","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: FOCS 2006. Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0167-6377(92)90007-P","volume":"11","author":"C.-L. Li","year":"1992","unstructured":"Li, C.-L., McCormick, S.T., Simchi\u2013Levi, D.: On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Operations Research Letters\u00a011, 303\u2013308 (1992)","journal-title":"Operations Research Letters"},{"key":"5_CR37","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/jgt.3190110315","volume":"11","author":"A.A. Schoone","year":"1987","unstructured":"Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. J. Graph Theory\u00a011, 409\u2013427 (1987)","journal-title":"J. Graph Theory"},{"key":"5_CR38","unstructured":"Shavitt, Y., Tankel, T.: On internet embedding in hyperbolic spaces for overlay construction and distance estimation. IEEE\/ACM Transactions on Networking and INFOCOM\u2019 2004. ACM Press, New York (to appear)"},{"key":"5_CR39","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T12:29:34Z","timestamp":1556800174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}