Augmenting the algebraic connectivity for certain families of graphs

Autor:	Anderson Chaves, Emanuelle Chaves, Claudia Marcela Justel, Carlos Rocha, Geraldo Avelino
Rok vydání:	2019
Předmět:	Discrete mathematics Random graph Algebraic connectivity Conjecture Applied Mathematics Discrete Mathematics and Combinatorics Perturbation (astronomy) Heuristics Graph Mathematics
Zdroj:	Discrete Applied Mathematics. 253:51-60
ISSN:	0166-218X
DOI:	10.1016/j.dam.2018.03.069
Popis:	In this work we compare solutions of two distinct algorithms that try to increase the value of the algebraic connectivity of a given graph by choosing, with different strategies, edges to be included. Eccentricity and Perturbation Heuristics were considered, as well as random graphs and special families of trees being inputs of those algorithms. As conclusions of the reported experiments, the Eccentricity Heuristic obtains good results when compared with Perturbation Heuristic and a conjecture about broom trees is presented.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d7e2254e6e9cb4c60373690cec97c8ea https://doi.org/10.1016/j.dam.2018.03.069 Zobrazit plný text záznamu Full Text from ScienceDirect