{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:56:02Z","timestamp":1648695362156},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00224-020-09977-6","type":"journal-article","created":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T13:02:52Z","timestamp":1586264572000},"page":"1094-1109","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem"],"prefix":"10.1007","volume":"64","author":[{"given":"Federico","family":"Cor\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahan","family":"Mkrtchyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"issue":"2","key":"9977_CR1","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1080\/15326340600649052","volume":"22","author":"K Avrachenkov","year":"2006","unstructured":"Avrachenkov, K., Litvak, N.: The effect of new links on google pagerank. Stoc. Models 22(2), 319\u2013331 (2006)","journal-title":"Stoc. Models"},{"key":"9977_CR2","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Basavaraju, M., Klinkby, K.V., Misra, P., Ramanujan, M.S., Saurabh, S., Zehavi, M.: Parameterized algorithms for survivable network design with uniform demands. In: 29Th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2838\u20132850 (2018)","DOI":"10.1137\/1.9781611975031.180"},{"key":"9977_CR3","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications. Springer (2008)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"9977_CR4","doi-asserted-by":"crossref","unstructured":"Basavaraju, M., Fomin, F.V., Golovach, P., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms to preserve connectivity. In: 41St International Colloquium on Automata, Languages and Programming (ICALP), pp. 800\u2013811 (2014)","DOI":"10.1007\/978-3-662-43948-7_66"},{"key":"9977_CR5","doi-asserted-by":"crossref","unstructured":"Bergamini, E., Crescenzi, P., D\u2019Angelo, G., Meyerhenke, H., Severini, L., Velaj, Y.: Improving the betweenness centrality of a node by adding links. ACM Journal of Experimental Algorithmics 23 (2018)","DOI":"10.1145\/3166071"},{"key":"9977_CR6","unstructured":"Cesati, M.: Compendium of parameterized problems. Department of Computer Science, Systems, and Industrial Engineering, University of Rome Tor Vergata 22 (2006)"},{"issue":"4","key":"9977_CR7","doi-asserted-by":"publisher","first-page":"1342","DOI":"10.1137\/120902847","volume":"43","author":"J Cheriyan","year":"2014","unstructured":"Cheriyan, J., V\u00e9gh, L.: Approximating minimum-cost k-node connected subgraphs via independence-free graphs. SIAM J. Comput. 43(4), 1342\u20131362 (2014)","journal-title":"SIAM J. Comput."},{"key":"9977_CR8","doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., D\u2019Angelo, G., Pinotti, C.M.: On the maximum connectivity improvement problem. In: 14Th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSOR) (2018)","DOI":"10.1007\/978-3-030-14094-6_4"},{"key":"9977_CR9","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., D\u2019Angelo, G., Severini, L., Velaj, Y.: Greedily improving our own centrality in a network. In: Proceedings of the 14th International Symposium on Experimental Algorithms (SEA 2015), LNCS, vol. 9125, pp. 43\u201355. Springer (2015)","DOI":"10.1007\/978-3-319-20086-6_4"},{"issue":"1","key":"9977_CR10","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2953882","volume":"11","author":"P Crescenzi","year":"2016","unstructured":"Crescenzi, P., D\u2019Angelo, G., Severini, L., Velaj, Y.: Greedily improving our own closeness centrality in a network. TKDD 11(1), 9:1\u20139:32 (2016)","journal-title":"TKDD"},{"issue":"3","key":"9977_CR11","doi-asserted-by":"publisher","first-page":"1503","DOI":"10.1137\/120883931","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Kortsarz, G., Nutov, Z.: Steiner forest orientation problems. SIAM J. Discrete Math. 27(3), 1503\u20131513 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"9977_CR12","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, G., Olsen, M., Severini, L.: Coverage centrality maximization in undirected networks. In: 33rd AAAI Conference on Artificial Intelligence (AAAI-19). To appear. CoRR arXiv:1811.04331 (2019)","DOI":"10.1609\/aaai.v33i01.3301501"},{"key":"9977_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Zadimoghaddam, M.: Minimizing the diameter of a network using shortcut edges. In: 12Th Scandinavian Symp. and Work. on Algorithm Theory (SWAT), LNCS, vol. 6139, pp. 420\u2013431. Springer (2010)","DOI":"10.1007\/978-3-642-13731-0_39"},{"issue":"4","key":"9977_CR14","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"KP Eswaran","year":"1976","unstructured":"Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5(4), 653\u2013665 (1976)","journal-title":"SIAM J. Comput."},{"key":"9977_CR15","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press (2011)"},{"issue":"10-11","key":"9977_CR16","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. Discret. Appl. Math. 161(10-11), 1626\u20131631 (2013)","journal-title":"Discret. Appl. Math."},{"key":"9977_CR17","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 Company, New York (1979)"},{"key":"9977_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.10.001","volume":"101","author":"G Gutin","year":"2019","unstructured":"Gutin, G., Ramanujan, M., Reidl, F., Wahlstr\u00f6m, M.: Path-contractions, edge deletions and connectivity preservation. J. Comput. Syst. Sci. 101, 1\u201320 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"9977_CR19","doi-asserted-by":"crossref","unstructured":"Hoffmann, C., Molter, H., Sorge, M.: The parameterized complexity of centrality improvement in networks. In: 44Th International Conference on Current Trends in Theory and Practice of Computer Science(SOFSEM 2018), pp. 111\u2013124 (2018)","DOI":"10.1007\/978-3-319-73117-9_8"},{"key":"9977_CR20","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum-cost connectivity problems. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC (2007)","DOI":"10.1201\/9781420010749.ch58"},{"issue":"4","key":"9977_CR21","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2700210","volume":"11","author":"D Marx","year":"2015","unstructured":"Marx, D., V\u00e9gh, L.A.: Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Trans. Algorithms 11(4), 27:1\u201327:24 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"9977_CR22","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Tagiku, B.: Minimizing average shortest path distances via shortcut edge addition. In: 13Th Int. Work. on Approx. Alg. for Comb. Opt. Prob. (APPROX), LNCS, vol. 5687, pp. 272\u2013285. Springer (2009)","DOI":"10.1007\/978-3-642-03685-9_21"},{"issue":"3","key":"9977_CR23","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/s00224-017-9786-5","volume":"62","author":"Z Nutov","year":"2018","unstructured":"Nutov, Z.: Improved approximation algorithms for minimum cost node-connectivity augmentation problems. Theor. Comput. Syst. 62(3), 510\u2013532 (2018)","journal-title":"Theor. Comput. Syst."},{"key":"9977_CR24","unstructured":"Nutov, Z., Gonzalez, T.F.: Node-connectivity survivable network problems. In: Handbook of Approximation Algorithms and Metaheuristics Contemporary and Emerging Applications, vol. 2. Taylor and Francis Group (2018)"},{"key":"9977_CR25","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2013.08.003","volume":"518","author":"M Olsen","year":"2014","unstructured":"Olsen, M., Viglas, A.: On the approximability of the link building problem. Theor. Comput. Sci. 518, 96\u2013116 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9977_CR26","first-page":"12","volume":"10","author":"M Papagelis","year":"2015","unstructured":"Papagelis, M.: Refining social graph connectivity via shortcut edge addition. ACM Trans. Knowl. Discov. Data (TKDD) 10(2), 12 (2015)","journal-title":"ACM Trans. Knowl. Discov. Data (TKDD)"},{"issue":"3","key":"9977_CR27","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3201775","volume":"10","author":"M Pilipczuk","year":"2018","unstructured":"Pilipczuk, M., Wahlstr\u00f6m, M.: Directed multicut is w[1]-hard, even for four terminal pairs. ACM Trans. Comput. Theory 10(3), 13:1\u201313:18 (2018)","journal-title":"ACM Trans. Comput. Theory"},{"key":"9977_CR28","doi-asserted-by":"crossref","unstructured":"Raghavan, S.: A note on eswaran and tarjan\u2019s algorithm for the strong connectivity augmentation. The Next Wave in Computing, Optimization, and Decision Technologies, pp. 19\u201326 (2005)","DOI":"10.1007\/0-387-23529-9_2"},{"key":"9977_CR29","unstructured":"Sas\u00e1k, R.: Comparing 17 Graph Parameters. Master thesis, University of Bergen (2010)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09977-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-020-09977-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09977-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T23:12:22Z","timestamp":1617750742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-020-09977-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,7]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["9977"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09977-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,7]]},"assertion":[{"value":"7 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}