{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:58Z","timestamp":1771036378480,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_55","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"678-688","source":"Crossref","is-referenced-by-count":8,"title":["Fast Algorithms for Diameter-Optimally Augmenting Paths"],"prefix":"10.1007","author":[{"given":"Ulrike","family":"Gro\u00dfe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Stehn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"55_CR1","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":"1999","unstructured":"Alon, N., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: Decreasing the diameter of bounded degree graphs. Journal of Graph Theory 35, 161\u2013172 (1999)","journal-title":"Journal of Graph Theory"},{"key":"55_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2011.05.014","volume":"417","author":"D Bil\u00f2","year":"2012","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Proietti, G.: Improved approximability and non-approximability results for graph diameter decreasing problems. Theoretical Computer Science 417, 12\u201322 (2012)","journal-title":"Theoretical Computer Science"},{"key":"55_CR3","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -nearest-neighbors and \n                    \n                      \n                    \n                    $$n$$\n                    \n                      \n                        n\n                      \n                    \n                  -body potential fields. Journal of the ACM 42, 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"issue":"2","key":"55_CR4","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 33(2), 243\u2013262 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"55_CR5","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1002\/jgt.3190080408","volume":"8","author":"FRK Chung","year":"1984","unstructured":"Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. Journal of Graph Theory 8(4), 511\u2013534 (1984)","journal-title":"Journal of Graph Theory"},{"key":"55_CR6","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750\u2013759 (1999)","DOI":"10.1145\/301250.301447"},{"issue":"4","key":"55_CR7","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s004930050035","volume":"18","author":"P Erd\u0151s","year":"1998","unstructured":"Erd\u0151s, P., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: How to decrease the diameter of triangle-free graphs. Combinatorica 18(4), 493\u2013501 (1998)","journal-title":"Combinatorica"},{"issue":"1","key":"55_CR8","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/050635675","volume":"38","author":"M Farshi","year":"2005","unstructured":"Farshi, M., Giannopoulos, P., Gudmundsson, J.: Improving the stretch factor of a geometric network by edge augmentation. SIAM Journal on Computing 38(1), 226\u2013240 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR9","doi-asserted-by":"crossref","unstructured":"Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting graphs to minimize the diameter. Algorithmica, 1\u201316 (2014)","DOI":"10.1007\/s00453-014-9886-4"},{"issue":"10\u201311","key":"55_CR10","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.1016\/j.dam.2013.01.016","volume":"161","author":"Y Gao","year":"2013","unstructured":"Gao, Y., Hare, D.R., Nastos, J.: The parametric complexity of graph diameter augmentation. Discrete Applied Mathematics 161(10\u201311), 1626\u20131631 (2013)","journal-title":"Discrete Applied Mathematics"},{"key":"55_CR11","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1002\/jgt.21719","volume":"74","author":"T Ishii","year":"2013","unstructured":"Ishii, T.: Augmenting outerplanar graphs to meet diameter requirements. Journal of Graph Theory 74, 392\u2013416 (2013)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"55_CR12","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s00224-006-1305-z","volume":"41","author":"S Kapoor","year":"2007","unstructured":"Kapoor, S., Sarwat, M.: Bounded-diameter minimum-cost graph problems. Theory of Computing Systems 41(4), 779\u2013794 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"5","key":"55_CR13","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-Levi, D.: On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Operations Research Letters 11(5), 303\u2013308 (1992)","journal-title":"Operations Research Letters"},{"key":"55_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1007\/978-3-540-92182-0_67","volume-title":"Algorithms and Computation","author":"J Luo","year":"2008","unstructured":"Luo, J., Wulff-Nilsen, C.: Computing best and worst shortcuts of graphs embedded in metric spaces. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 764\u2013775. Springer, Heidelberg (2008)"},{"issue":"2","key":"55_CR15","doi-asserted-by":"publisher","first-page":"599","DOI":"10.7155\/jgaa.00275","volume":"16","author":"I Rutter","year":"2012","unstructured":"Rutter, I., Wolff, A.: Augmenting the connectivity of planar and geometric graphs. Journal of Graph Algorithms and Applications 16(2), 599\u2013628 (2012)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"55_CR16","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/jgt.3190110315","volume":"11","author":"AA Schoone","year":"1997","unstructured":"Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. Journal of Graph Theory 11, 409\u2013427 (1997)","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"55_CR17","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.comgeo.2009.03.008","volume":"43","author":"C Wulff-Nilsen","year":"2010","unstructured":"Wulff-Nilsen, C.: Computing the dilation of edge-augmented graphs in metric spaces. Computational Geometry - Theory and Applications 43(2), 68\u201372 (2010)","journal-title":"Computational Geometry - Theory and Applications"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T07:20:22Z","timestamp":1559200822000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}