{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:06:29Z","timestamp":1768107989265,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642190933","type":"print"},{"value":"9783642190940","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19094-0_4","type":"book-chapter","created":{"date-parts":[[2011,2,10]],"date-time":"2011-02-10T06:21:40Z","timestamp":1297318900000},"page":"9-20","source":"Crossref","is-referenced-by-count":13,"title":["Maximum Betweenness Centrality: Approximability and Tractable Cases"],"prefix":"10.1007","author":[{"given":"Martin","family":"Fink","sequence":"first","affiliation":[]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.A. Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 17\u201330. Springer, Heidelberg (1999)"},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","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. Journal of Mathematical Sociology\u00a025(2), 163\u2013177 (2001)","journal-title":"Journal of Mathematical Sociology"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","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. Social Networks\u00a030(2), 136\u2013145 (2008)","journal-title":"Social Networks"},{"issue":"20","key":"4_CR4","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.1016\/j.ipl.2009.07.019","volume":"109","author":"S. Dolev","year":"2009","unstructured":"Dolev, S., Elovici, Y., Puzis, R., Zilberman, P.: Incremental deployment of network monitors based on group betweenness centrality. Information Processing Letters\u00a0109(20), 1172\u20131176 (2009), \n                    \n                      http:\/\/www.sciencedirect.com\/science\/article\/B6V0F-4X01PFN-1\/2\/2798e8bf8a2975f8024bcc2f8b8873ac","journal-title":"Information Processing Letters"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1080\/0022250X.1999.9990219","volume":"23","author":"M. Everett","year":"1999","unstructured":"Everett, M., Borgatti, S.: The centrality of groups and classes. Journal of Mathematical Sociology\u00a023, 181\u2013202 (1999)","journal-title":"Journal of Mathematical Sociology"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"L. Freeman","year":"1977","unstructured":"Freeman, L.: A set of measures of centrality based on betweenness. Sociometry\u00a040(1), 35\u201341 (1977)","journal-title":"Sociometry"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Information Processing Letters\u00a070, 39\u201345 (1999)","journal-title":"Information Processing Letters"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"16132","DOI":"10.1103\/PhysRevE.64.016132","volume":"64","author":"M.E.J. Newman","year":"2001","unstructured":"Newman, M.E.J.: Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E\u00a064, 16132 (2001)","journal-title":"Physical Review E"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: Gap location. Computational Complexity\u00a04, 133\u2013157 (1994)","journal-title":"Computational Complexity"},{"issue":"4","key":"4_CR11","first-page":"287","volume":"20","author":"R. Puzis","year":"2007","unstructured":"Puzis, R., Elovici, Y., Dolev, S.: Finding the most prominent group in complex networks. AI Communications\u00a020(4), 287\u2013296 (2007)","journal-title":"AI Communications"},{"issue":"5","key":"4_CR12","doi-asserted-by":"publisher","first-page":"56709","DOI":"10.1103\/PhysRevE.76.056709","volume":"76","author":"R. Puzis","year":"2007","unstructured":"Puzis, R., Elovici, Y., Dolev, S.: Fast algorithm for successive computation of group betweenness centrality. Phys. Rev. E\u00a076(5), 56709 (2007)","journal-title":"Phys. Rev. E"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters\u00a032(1), 41\u201343 (2004)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19094-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,24]],"date-time":"2019-03-24T07:32:39Z","timestamp":1553412759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19094-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642190933","9783642190940"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19094-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}