In Search of Robust and Efficient Sparse Networks

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

DOI: https://doi.org/10.5753/wperformance.2022.223313

Abstract

Motivated by the importance of building sparse, efficient and robust networks, we consider sparse networks with small sum of distances across nodes (Wiener index) and that are robust (biconnected). In particular, we propose a novel efficient algorithm to compute the Wiener index for those sparse networks. The algorithm allows us to exhaustively compute the Wiener index for a class of graphs with up to 20 vertices, verifying interesting properties of those graphs.

Keywords: graphs, algorithms on graphs, Wiener index, sparse

References

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.