{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:57:34Z","timestamp":1755838654807},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_8","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T11:45:34Z","timestamp":1513856734000},"page":"111-124","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Parameterized Complexity of Centrality Improvement in Networks"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Hoffmann","sequence":"first","affiliation":[]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-642-17493-3_4","volume-title":"Parameterized and Exact Computation","author":"AM Ambalath","year":"2010","unstructured":"Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14\u201325. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-17493-3_4"},{"issue":"2","key":"8_CR2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theor. Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001)","journal-title":"J. Math. Sociol."},{"issue":"2","key":"8_CR4","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.socnet.2007.11.001","volume":"30","author":"U Brandes","year":"2008","unstructured":"Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136\u2013145 (2008)","journal-title":"Soc. Netw."},{"issue":"1","key":"8_CR5","doi-asserted-by":"crossref","first-page":"9","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. ACM Trans. Knowl. Discov. Data 11(1), 9 (2016)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"2","key":"8_CR6","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1093\/comnet\/cnt016","volume":"1","author":"P Csermely","year":"2013","unstructured":"Csermely, P., London, A., Wu, L.-Y., Uzzi, B.: Structure and dynamics of core\/periphery networks. J. Complex Netw. 1(2), 93\u2013123 (2013)","journal-title":"J. Complex Netw."},{"key":"8_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.entcs.2016.03.011","volume":"322","author":"G D\u2019Angelo","year":"2016","unstructured":"D\u2019Angelo, G., Severini, L., Velaj, Y.: On the maximum betweenness improvement problem. Electron. Notes Theor. Comput. Sci. 322, 153\u2013168 (2016)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"2","key":"8_CR9","doi-asserted-by":"crossref","first-page":"543","DOI":"10.7155\/jgaa.00273","volume":"16","author":"D Eppstein","year":"2012","unstructured":"Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543\u2013567 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40, 35\u201341 (1977)","journal-title":"Sociometry"},{"issue":"3","key":"8_CR11","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","volume":"1","author":"LC Freeman","year":"1978","unstructured":"Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215\u2013239 (1978)","journal-title":"Soc. Netw."},{"issue":"1","key":"8_CR12","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196\u2013217 (2010)","journal-title":"Theory Comput. Syst."},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-SAT. In: Proceeding of the 14th Annual IEEE Conference on Computational Complexity (CCC 1999), pp. 237\u2013240 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? In: Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 653\u2013662 (1998)","DOI":"10.1109\/SFCS.1998.743516"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-319-03898-8_22","volume-title":"Parameterized and Exact Computation","author":"D Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Misra, N., Philip, G., Ramanujan, M.S., Saurabh, S.: Hardness of r-dominating set on Graphs of Diameter (\n            $$r + 1$$\n            \n              \n                \n                  r\n                  +\n                  1\n                \n              \n            \n          ). In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 255\u2013267. Springer, Cham (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-319-03898-8_22"},{"key":"8_CR16","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman, M.: Networks: An Introduction. Oxford University Press, Oxford (2010)"},{"issue":"1","key":"8_CR17","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.socnet.2004.11.009","volume":"27","author":"ME Newman","year":"2005","unstructured":"Newman, M.E.: A measure of betweenness centrality based on random walks. Soc. Netw. 27(1), 39\u201354 (2005)","journal-title":"Soc. Netw."},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-540-69311-6_21","volume-title":"Frontiers in Algorithmics","author":"K Okamoto","year":"2008","unstructured":"Okamoto, K., Chen, W., Li, X.-Y.: Ranking of closeness centrality for large-scale social networks. In: Preparata, F.P., Wu, X., Yin, J. (eds.) FAW 2008. LNCS, vol. 5059, pp. 186\u2013195. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-69311-6_21"},{"issue":"3","key":"8_CR19","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.socnet.2010.03.006","volume":"32","author":"T Opsahl","year":"2010","unstructured":"Opsahl, T., Agneessens, F., Skvoretz, J.: Node centrality in weighted networks: generalizing degree and shortest paths. Soc. Netw. 32(3), 245\u2013251 (2010)","journal-title":"Soc. Netw."},{"key":"8_CR20","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2016","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 5th edn. Springer, Heidelberg (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"5"},{"issue":"3","key":"8_CR21","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/j.neuroimage.2009.10.003","volume":"52","author":"M Rubinov","year":"2010","unstructured":"Rubinov, M., Sporns, O.: Complex network measures of brain connectivity: uses and interpretations. Neuroimage 52(3), 1059\u20131069 (2010)","journal-title":"Neuroimage"},{"issue":"4","key":"8_CR22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0378-8733(94)90015-9","volume":"16","author":"DR White","year":"1994","unstructured":"White, D.R., Borgatti, S.P.: Betweenness centrality measures for directed graphs. Soc. Netw. 16(4), 335\u2013346 (1994)","journal-title":"Soc. Netw."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T11:48:44Z","timestamp":1513856924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}