Utilização da Árvore SPQR para um Cálculo Mais Eficiente das Medidas de Conectividade Baseadas em Cortes de Vértices
Abstract
The connectivity measure κ2 (v) of a vertex v of graph G is the maximum number of vertex-disjoint paths between v and any other vertex of the graph. The purpose of this work is to improve the efficiency for computing κ2 (v). A pre-processing step is proposed in which a SPQR tree is buit that identifies all tri-connected components of the graph. Thus, κ2 (v) can be computed separately for each component. The proposal was implemented and tested in graphs that model concrete cases. Experimental results are presented showing that for graphs for which the proposed strategy does improve the efficiency for computing κ2 (v), in comparison with the original approach.
References
Cohen, J., Duarte, E. P. and Schroeder, J. (2011). Connectivity Criteria for Ranking Network Nodes, Communications in Computer and Information Science (CCIS), Vol. 116. pp. 35-45.
Cohen, J. (2013). Algoritmos Paralelos para Árvores de Cortes e Medidas de Centralidade em Grafos, Tese de Doutorado, Departamento de Informática - Universidade Federal do Paraná,
Pires, K., Cohen, J. and Duarte, E. P. (2011). Medidas de Conectividade Baseadas em Cortes de Vertices para Redes Complexas, 12 Workshop de Testes e Tolerância a Falhas (WTF’2011), Anais do SBRC’2011.
Pires, K. (2011). Medidas de Conectividade Baseadas em Cortes de Vértices para Redes Complexas, Dissertação de Mestrado, Departamento de Informática - Universidade Federal do Paraná.
Gutwenger, C. (2010). Application of SPQR-Trees in the Planarization Approach for Drawing Graphs, Tese de Doutorado, Technischen Universität Dortmund an der Fakultät für Informatik.
Batagelj, V. and Mrvar, A. (2006). Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em dezembro de 2015.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity, Cambridge University Press.
Duarte, E. P., Santini, R. and Cohen, J. (2004). Delivering Packets During the Routing Convergence Latency Interval Through Highly Connected Detours, DSN, pp. 495–. IEEE Computer Society.
Hopcroft, J. E. and Tarjan, R. E. (1972). Finding the Triconected Components of a Graph, Technical Report 72-140, Cornell University.
Di Battista, G. and Tamassia, R. (1996). On-Line Maintenance of Triconnected Components with SPQR-Trees, Algorithmica, Vol. 15, pp. 302-318.
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., Li, G., Chen, R. (2003). Topological Structure Analysis of the Protein-protein Interaction Network in Budding Yeast, Nucleic acids research, Vol. 31(9), pp. 2443–2450.
Storchi, G., Dell’Olmo, P. and Gentili, M. (1999) Directed Road Network of the City of Rome (1999). Disponível em [link], acessado em dezembre de 2015.
Kleinberg, J. M., Leskovec J. and Faloutsos, C. (2007). Graph Evolution: Densification and Shrinking Diameters, ACM Transactions on Knowledge Discovery from Data (ACM TKDD).
Watts, D. J. and Strogatz, S. H. (1998). Collective Dynamics of ’Small-World’ Networks, Nature, Vol. 393(6684), pp. 440–442.
Cohen, J. (2013). Algoritmos Paralelos para Árvores de Cortes e Medidas de Centralidade em Grafos, Tese de Doutorado, Departamento de Informática - Universidade Federal do Paraná,
Pires, K., Cohen, J. and Duarte, E. P. (2011). Medidas de Conectividade Baseadas em Cortes de Vertices para Redes Complexas, 12 Workshop de Testes e Tolerância a Falhas (WTF’2011), Anais do SBRC’2011.
Pires, K. (2011). Medidas de Conectividade Baseadas em Cortes de Vértices para Redes Complexas, Dissertação de Mestrado, Departamento de Informática - Universidade Federal do Paraná.
Gutwenger, C. (2010). Application of SPQR-Trees in the Planarization Approach for Drawing Graphs, Tese de Doutorado, Technischen Universität Dortmund an der Fakultät für Informatik.
Batagelj, V. and Mrvar, A. (2006). Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em dezembro de 2015.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity, Cambridge University Press.
Duarte, E. P., Santini, R. and Cohen, J. (2004). Delivering Packets During the Routing Convergence Latency Interval Through Highly Connected Detours, DSN, pp. 495–. IEEE Computer Society.
Hopcroft, J. E. and Tarjan, R. E. (1972). Finding the Triconected Components of a Graph, Technical Report 72-140, Cornell University.
Di Battista, G. and Tamassia, R. (1996). On-Line Maintenance of Triconnected Components with SPQR-Trees, Algorithmica, Vol. 15, pp. 302-318.
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., Li, G., Chen, R. (2003). Topological Structure Analysis of the Protein-protein Interaction Network in Budding Yeast, Nucleic acids research, Vol. 31(9), pp. 2443–2450.
Storchi, G., Dell’Olmo, P. and Gentili, M. (1999) Directed Road Network of the City of Rome (1999). Disponível em [link], acessado em dezembre de 2015.
Kleinberg, J. M., Leskovec J. and Faloutsos, C. (2007). Graph Evolution: Densification and Shrinking Diameters, ACM Transactions on Knowledge Discovery from Data (ACM TKDD).
Watts, D. J. and Strogatz, S. H. (1998). Collective Dynamics of ’Small-World’ Networks, Nature, Vol. 393(6684), pp. 440–442.
Published
2016-05-30
How to Cite
HEPP, Henrique; COHEN, Jaime; DUARTE JR., Elias Procópio.
Utilização da Árvore SPQR para um Cálculo Mais Eficiente das Medidas de Conectividade Baseadas em Cortes de Vértices. In: FAULT TOLERANCE WORKSHOP (WTF), 17. , 2016, Salvador/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 16-27.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2016.22873.
