Em Busca de Redes Esparsas Robustas e Eficientes

  • Romeu Lustosa Pires UFRJ / Anlix
  • Carlos Bravo Serrado UFRJ
  • Daniel Sadoc Menasché UFRJ

Resumo


Motivados pela importância de construir redes eficientes e robustas, apresentamos um algoritmo eficiente para calcular a soma das distâncias em redes esparsas. Tal índice, também chamado de índice de Wiener, está relacionado com a eficiência da rede. Aplicando o algoritmo, discutimos algumas propriedades das redes robustas (biconexas) e eficientes (com pequena soma das distâncias).
Palavras-chave: grafos, algoritmos em grafos, índice de Wiener, esparsidade, biconectividade

Referências

Bollobás, B. (2004). Extremal graph theory. Courier Corporation.

Brendan McKay, Adolfo Piperno (2022). Nauty traces. Acessado em 7 abril 2022.

Chepoi, V. and Klavzar, S. (1997). The Wiener index and the Szeged index of benzenoid systems in linear time. Journal of chemical info. computer science, 37(4):752–755.

Dankelmann, P., Gutman, I., Mukwembi, S., and Swart, H. C. (2009). The edge-wiener index of a graph. Discrete Mathematics, 309(10):3452–3457.

Deng, H., Xiao, H., and Tang, F. (2010). On the extremal wiener polarity index of trees with a given diameter. MATCH Commun. Math. Comput. Chem, 63(1):257–264.

Graovac, A. and Pisanski, T. (1991). On the wiener index of a graph. Journal of mathematical chemistry, 8(1):53–62.

Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530.

Klavzar, S., Gutman, I., and Mohar, B. (1995). Labeling of benzenoid systems which reflects the vertexdistance relations. Journal of chemical info. and comp. sci., 35(3):590–593.

Mohar, B. and Pisanski, T. (1988). How to compute the Wiener index of a graph. Journal of mathematical chemistry, 2(3):267–277.

Paul Manuel, Indra Rajasingh, Bharati Rajan, R. Sundara Rajan (2013). A new approach to compute wiener index. Journal Computational Theoretical Nanoscience https://arxiv.org/abs/1307.6502.

Roditty, L. and Vassilevska Williams, V. (2013). Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524.

Yeh, Y.-N. and Gutman, I. (1994). On the sum of all distances in composite graphs. Discrete Mathematics, 135(1-3):359–365.
Publicado
31/07/2022
PIRES, Romeu Lustosa; SERRADO, Carlos Bravo; MENASCHÉ, Daniel Sadoc. Em Busca de Redes Esparsas Robustas e Eficientes. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 21. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 114-119. ISSN 2595-6167. DOI: https://doi.org/10.5753/wperformance.2022.223313.