{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:34Z","timestamp":1771036354528,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,16]],"date-time":"2014-05-16T00:00:00Z","timestamp":1400198400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9886-4","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T18:08:08Z","timestamp":1400177288000},"page":"995-1010","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["Augmenting Graphs to Minimize the Diameter"],"prefix":"10.1007","volume":"72","author":[{"given":"Fabrizio","family":"Frati","sequence":"first","affiliation":[]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[]},{"given":"Luke","family":"Mathieson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,16]]},"reference":[{"key":"9886_CR1","doi-asserted-by":"crossref","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. J. Graph Theory 35, 161\u2013172 (1999)","journal-title":"J. Graph Theory"},{"key":"9886_CR2","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 417, 12\u201322 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9886_CR3","doi-asserted-by":"crossref","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"},{"key":"9886_CR4","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Zadimoghaddam, M.: Minimizing the diameter of a network using shortcut edges. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 420\u2013431 (2010)","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"9886_CR5","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"},{"key":"9886_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer (1999)"},{"key":"9886_CR7","first-page":"215","volume":"1","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., R\u00e9nyi, A., S\u00f3s, V.T.: On a problem of graph theory. Studia Sci. Math. Hungar 1, 215\u2013235 (1966)","journal-title":"Studia Sci. Math. Hungar"},{"key":"9886_CR8","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006)"},{"key":"9886_CR9","doi-asserted-by":"crossref","unstructured":"Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting graphs to minimize the diameter. In: Cai, L., Cheng, S.W., Lam, T.W. (eds.) International Symposium on Algorithms and Computation (ISAAC \u201913). LNCS, vol. 8283, pp. 383\u2013393. Springer (2013)","DOI":"10.1007\/978-3-642-45030-3_36"},{"issue":"3","key":"9886_CR10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"9886_CR11","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"ML Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"10\u201311","key":"9886_CR12","doi-asserted-by":"crossref","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. Discret. Appl. Math. 161(10\u201311), 1626\u20131631 (2013)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"9886_CR13","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1002\/jgt.10122","volume":"43","author":"E Grigorescu","year":"2003","unstructured":"Grigorescu, E.: Decreasing the diameter of cycles. J. Graph Theory 43(4), 299\u2013303 (2003)","journal-title":"J. Graph Theory"},{"issue":"4","key":"9886_CR14","doi-asserted-by":"crossref","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 Comput. Syst. 41(4), 779\u2013794 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"9886_CR15","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0167-6377(92)90007-P","volume":"11","author":"CL 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. Oper. Res. Lett. 11(5), 303\u2013308 (1992)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9886_CR16","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"9886_CR17","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"9886_CR18","doi-asserted-by":"crossref","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. J. Graph Theory 11, 409\u2013427 (1997)","journal-title":"J. Graph Theory"},{"key":"9886_CR19","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9886-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9886-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9886-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T13:59:49Z","timestamp":1565445589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9886-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,16]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9886"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9886-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,16]]}}}