Back to Search
Start Over
COMPUTING WEIGHTED STRENGTH AND APPLICATIONS TO PARTITIONING.
- Source :
-
SIAM Journal on Discrete Mathematics . 2018, Vol. 32 Issue 4, p2747-2782. 36p. - Publication Year :
- 2018
-
Abstract
- 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+ε the weighted strength in time O(mlog(W)log³(n)/ε²), and that can be implemented with O(m) memory use if we allow a complexity of O(mlog²(W)log³(n)/ε²). 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH algorithms
*GRAPH connectivity
*DENSE graphs
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 32
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 136077841
- Full Text :
- https://doi.org/10.1137/15M102914X