Geodesic
Bounds and algorithms for graph trusses
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 191-214.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The $k$-truss, introduced by Cohen (2005), is a graph where every edge is incident to at least $k$ triangles. This is a relaxation of the clique. It has proved to be a useful tool in identifying cohesive subnetworks in a variety of real-world graphs. Despite its simplicity and its utility, the combinatorial and algorithmic aspects of trusses have not been thoroughly explored. We provide nearly-tight bounds on the edge counts of $k$-trusses. We also give two improved algorithms for finding trusses in large-scale graphs. First, we present a simplified and faster algorithm, based on approach discussed in Wang Cheng (2012). Second, we present a theoretical algorithm based on fast matrix multiplication; this converts a triangle-generation algorithm of Björklund et al. (2014) into a dynamic data structure.
DOI : 10.7155/jgaa.00527
Keywords: Graph algorithms, Truss, Dense cores, Cohesive subnetwork 
@article{JGAA_2020_24_3_a3,
     author = {Paul Burkhardt and Vance Faber and David Harris},
     title = {Bounds and algorithms for graph trusses},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {191--214},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00527},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00527/}
}
TY  - JOUR
AU  - Paul Burkhardt
AU  - Vance Faber
AU  - David Harris
TI  - Bounds and algorithms for graph trusses
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 191
EP  - 214
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00527/
DO  - 10.7155/jgaa.00527
LA  - en
ID  - JGAA_2020_24_3_a3
ER  - 
%0 Journal Article
%A Paul Burkhardt
%A Vance Faber
%A David Harris
%T Bounds and algorithms for graph trusses
%J Journal of Graph Algorithms and Applications
%D 2020
%P 191-214
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00527/
%R 10.7155/jgaa.00527
%G en
%F JGAA_2020_24_3_a3
Paul Burkhardt; Vance Faber; David Harris. Bounds and algorithms for graph trusses. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 191-214. doi : 10.7155/jgaa.00527. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00527/

Cité par Sources :