Marches optimales sur les graphes et matrices tropicales

Glenn Merlet
I2M, Aix-Marseille Université
/user/glenn.merlet/

Date(s) : 09/06/2015   iCal
11 h 05 min - 12 h 20 min

Les puissances des matrices à coefficients dans le semianneau dit tropical, sont données par les poids de marches sur des graphes pondérés, optimales en certains sens.
En manipulant les marches en question, on peut borner le temps d’atteinte des régime asymptotique pour les puissances, généralisant ainsi des résultats classiques sur les matrices booléennes/positives.

Il s’agit d’un travail commun avec T. Nowak, H. Schneider et S. Sergeev.

Optimal walks on tropical graphs and matrices

The powers of the matrices with coefficients in the so-called tropical semiring are given by the weights of walks on weighted graphs, optimal in certain senses.

By manipulating the walks in question, we can limit the time to reach the asymptotic regime for the powers, thus generalizing classical results on Boolean/positive matrices.

This is a joint work with T. Nowak, H. Schneider and S. Sergeev.

https://arxiv.org/abs/1307.3716

 

Catégories



Retour en haut