Geodesic
Time Windowed Data Structures for Graphs
Journal of graph algorithms and applications, Tome 23 (2019) no. 2, pp. 191-226 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We present data structures that can answer time windowed queries for a set of timestamped events in a relational event graph. We study the relational event graph as input to solve (a) time windowed decision problems for monotone graph properties, such as disconnectedness and bipartiteness, and (b) time windowed reporting problems such as reporting the minimum spanning tree, the minimum time interval, and the graph edit distance for obtaining spanning forests. We also present results of window queries for counting subgraphs of a given pattern, such as paths of length 2 (in general graphs) and paths of length 3 (in bipartite graphs), quadrangles and complete subgraphs of a fixed order or of all orders $\ell \geq 3$ (i.e., cliques of size $\ell$). These query results can be used to compute graph parameters that are important for social network analysis, e.g., clustering coefficients, embeddedness and neighborhood overlapping. 
@article{JGAA_2019_23_2_a3,
     author = {Farah Chanchary and Anil Maheshwari},
     title = {Time {Windowed} {Data} {Structures} for {Graphs}},
     journal = {Journal of graph algorithms and applications},
     pages = {191--226},
     year = {2019},
     volume = {23},
     number = {2},
     doi = {10.7155/jgaa.00489},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00489/}
}
TY  - JOUR
AU  - Farah Chanchary
AU  - Anil Maheshwari
TI  - Time Windowed Data Structures for Graphs
JO  - Journal of graph algorithms and applications
PY  - 2019
SP  - 191
EP  - 226
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00489/
DO  - 10.7155/jgaa.00489
LA  - en
ID  - JGAA_2019_23_2_a3
ER  - 
%0 Journal Article
%A Farah Chanchary
%A Anil Maheshwari
%T Time Windowed Data Structures for Graphs
%J Journal of graph algorithms and applications
%D 2019
%P 191-226
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00489/
%R 10.7155/jgaa.00489
%G en
%F JGAA_2019_23_2_a3
Farah Chanchary; Anil Maheshwari. Time Windowed Data Structures for Graphs. Journal of graph algorithms and applications, Tome 23 (2019) no. 2, pp. 191-226. doi: 10.7155/jgaa.00489

Cité par Sources :