{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:36:16Z","timestamp":1742913376852,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319202969"},{"type":"electronic","value":"9783319202976"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20297-6_9","type":"book-chapter","created":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T01:55:05Z","timestamp":1434938105000},"page":"123-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Polynomial-Time Algorithm for Outerplanar Diameter Improvement"],"prefix":"10.1007","author":[{"given":"Nathann","family":"Cohen","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Gon\u00e7alves","sequence":"additional","affiliation":[]},{"given":"Eunjung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-642-28050-4_7","volume-title":"Parameterized and Exact Computation","author":"I Adler","year":"2012","unstructured":"Adler, I., Kolliopoulos, S.G., Thilikos, D.M.: Planar disjoint-paths completion. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 80\u201393. Springer, Heidelberg (2012)"},{"issue":"3","key":"9_CR2","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 Theor. 35(3), 161\u2013172 (2000)","journal-title":"J. Graph Theor."},{"key":"9_CR3","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. Theor. Comput. Sci. 417, 12\u201322 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9_CR4","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 45(2), 209\u2013226 (2006)","journal-title":"Algorithmica"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Cohen, N., Gon\u00e7alves, D., Kim, E.J., Paul, C., Sau, I., Thilikos, D.M., Weller, M.: A polynomial-time algorithm for outerplanar diameter improvement. CoRR, abs\/1403.5702 (2014)","DOI":"10.1007\/978-3-319-20297-6_9"},{"issue":"3","key":"9_CR6","first-page":"376","volume":"58","author":"P Dankelmann","year":"2014","unstructured":"Dankelmann, P., Erwin, D., Goddard, W., Mukwembi, S., Swart, H.: A characterisation of eccentric sequences of maximal outerplanar graphs. Australas. J. Comb. 58(3), 376\u2013391 (2014)","journal-title":"Australas. J. Comb."},{"key":"9_CR7","unstructured":"Dejter, I.J., Fellows, M.: Improving the diameter of a planar graph. Technical report, Computer Science department at the University of Victoria, May 1993"},{"key":"9_CR8","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Design 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":"9_CR10","doi-asserted-by":"publisher","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. Springer, New York (1999)"},{"issue":"4","key":"9_CR11","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-free graphs. Combinatorica 18(4), 493\u2013501 (1998)","journal-title":"Combinatorica"},{"key":"9_CR12","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-642-45030-3_36","volume-title":"Algorithms and Computation","author":"F Frati","year":"2013","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.) Algorithms and Computation. LNCS, vol. 8283, pp. 383\u2013393. Springer, Heidelberg (2013)"},{"key":"9_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"issue":"3","key":"9_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"MC Golumbic","year":"1994","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Adv. Appl. Math. 15(3), 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion with few edges. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 374\u2013381(2007)","DOI":"10.1145\/1250790.1250847"},{"issue":"4","key":"9_CR17","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. J. Graph Theor. 74(4), 392\u2013416 (2013)","journal-title":"J. Graph Theor."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Jasine, B., Basavaraju, M., Chandran, L.S., Rajendraprasad, D.: 2-connecting outerplanar graphs without blowing up the pathwidth. Theor. Comput. Sci. (2014, to appear). http:\/\/dx.doi.org\/10.1016\/j.tcs.2014.04.032","DOI":"10.1016\/j.tcs.2014.04.032"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1996.0034","volume":"21","author":"G Kant","year":"1996","unstructured":"Kant, G.: Augmenting outerplanar graphs. J. Algorithms 21(1), 1\u201325 (1996)","journal-title":"J. Algorithms"},{"issue":"5","key":"9_CR20","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"key":"9_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Kettering (2006)"},{"issue":"1","key":"9_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"2","key":"9_CR23","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Com. Theor. Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Com. Theor. Ser. B"},{"issue":"1","key":"9_CR24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Computer Science -- Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20297-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T12:52:36Z","timestamp":1675860756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20297-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319202969","9783319202976"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20297-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}