{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:45:50Z","timestamp":1787319950802,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with $n$ vertices and $m$ weighted edges, we denote by $W$ the total sum of the integer weights, and we describe an algorithm that approximates within a factor of $1+\\varepsilon$ the weighted strength in time $O(m\\log(W)\\log^3(n)\/\\varepsilon^2)$, and that can be implemented with $O(m)$ memory use if we allow a complexity of $O(m\\log^2(W)\\log^3(n)\/\\varepsilon^2)$. This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning.<\/jats:p>","DOI":"10.1137\/15m102914x","type":"journal-article","created":{"date-parts":[[2018,11,29]],"date-time":"2018-11-29T11:29:01Z","timestamp":1543490941000},"page":"2747-2782","source":"Crossref","is-referenced-by-count":1,"title":["Computing Weighted Strength and Applications to Partitioning"],"prefix":"10.1137","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5566-2314","authenticated-orcid":true,"given":"Jerome","family":"Galtier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90045-5"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90013-2"},{"key":"atypb4","unstructured":"T. Cormen, C. Leiserson, R. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , MIT Press, Cambridge, MA, 2009."},{"key":"atypb5","unstructured":"KDD Cup 2003\n                      , Cornell University, Ithaca, NY."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3829"},{"key":"atypb7","first-page":"185","author":"Edmonds J.","year":"1977","journal-title":"Amsterdam"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"atypb9","first-page":"88","author":"Gabow H. N.","year":"1995","journal-title":"Philadelphia"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585866"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-018-2756-8"},{"key":"atypb12","first-page":"300","author":"Garg N.","year":"1998","journal-title":"IEEE"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0220040"},{"key":"atypb15","first-page":"257","author":"Hoerdt M.","year":"2003","journal-title":"Telecommunications and Computer Networks"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90012-3"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"atypb18","first-page":"217","author":"Kelner J. A.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb19","unstructured":"E. Lawler,\n                      Combinatorial Optimization: Networks and Matroids\n                      , Holt, Rinehart and Winston, 1976."},{"key":"atypb20","first-page":"500","author":"Matula D. W.","year":"1993","journal-title":"Philadelphia"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"K. Murota,\n                      Matrices and Matroids for Systems Analysis\n                      , Springer, 2009.","DOI":"10.1007\/978-3-642-03994-2"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"atypb23","first-page":"12","volume":"39","author":"St C.","year":"1964","journal-title":"J. London Math. Soc."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"J. Orlin,\n                      Max flows in O(nm) time, or better\n                      , in Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 765-774.","DOI":"10.1145\/2488608.2488705"},{"key":"atypb27","unstructured":"J. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, New York, 1992."},{"key":"atypb28","unstructured":"G. Palaiopanos, I. Panageas, and G. Piliouras,\n                      Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos\n                      , preprint,https:\/\/arxiv.org\/abs\/1703.01138, 2017."},{"key":"atypb29","first-page":"495","author":"Plotkin S.","year":"1991","journal-title":"IEEE"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.01.040"},{"key":"atypb31","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\n                      , Springer, 2003."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374402"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.10.023"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01125543"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"J. S. Vitter,\n                      Algorithms and Data Structures for External Memory\n                      , now Publishers Inc., Hanover, MA, 2008.","DOI":"10.1561\/0400000014"},{"key":"atypb37","first-page":"170","author":"Young N. E.","year":"1995","journal-title":"Philadelphia"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M102914X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:09Z","timestamp":1787316849000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M102914X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M102914X"],"URL":"https:\/\/doi.org\/10.1137\/15m102914x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}