Centre de documentation
scientifique

Generalizations of bounds on the index of convergence to weighted digraphs / Glenn Merlet in Discrete Applied Mathematics, vol 178 ([11/12/2014])  

Public [article]  inDiscrete Applied Mathematics > vol 178 [11/12/2014] . - pp 121 - 134 Titre : Generalizations of bounds on the index of convergence to weighted digraphs Type de document : Article/Communication Auteurs : Glenn Merlet, Auteur ; Thomas Nowak, Auteur ; Hans Schneider, Auteur ; Sergeĭ Sergeev, Auteur Année de publication : 2014 Article en page(s) : pp 121 - 134 Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse numérique [Termes IGN] convergence [Termes IGN] factorisation de matrice non-négative [Termes IGN] graphe [Termes IGN] matrice [Termes IGN] recherche du chemin optimal, algorithme de Index. décimale : 23.40 Analyse numérique Résumé : (auteur) We study sequences of optimal walks of a growing length in weighted digraphs, or equivalently, sequences of entries of max-algebraic matrix powers with growing exponents. It is known that these sequences are eventually periodic when the digraphs are strongly connected. The transient of such periodicity depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that some bounds on the indices of periodicity of (unweighted) digraphs, such as the bounds of Wielandt, Dulmage–Mendelsohn, Schwarz, Kim and Gregory–Kirkland–Pullman, apply to the weights of optimal walks when one of their ends is a critical node. Numéro de notice : A2014-600 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/MATHEMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1016/j.dam.2014.06.026 En ligne : https://doi.org/10.1016/j.dam.2014.06.026 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=74894 [article]