# The Eulerian stretch of a digraph and the ending guarantee of a convergence routing

1 OPALE - Optimization and control, numerical algorithms and integration of complex multidiscipline systems governed by PDE
CRISAM - Inria Sophia Antipolis - Méditerranée , JAD - Laboratoire Jean Alexandre Dieudonné : UMR6621
3 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we focus on convergence packet routing techniques in a network, obtained from an Eulerian routing in the digraph modeling the target network. Given an Eulerian circuit $\cal C$ in a digraph $G$, we consider the maximal number $diamW_{\cal C}$ of arcs that a packet has to follow on $\cal C$ from its origin to its destination (we talk about the {\em ending guarantee} of the routing). We consider the {\em Eulerian diameter of $G$} as defined by ${\cal E}(G)=\min\limits_{{\cal C}? Eul(G)} diamW_{\cal C}$, where $Eul(G)$ is the set of all the Eulerian circuits in $G$. After giving a preliminary result about the complexity of finding ${\cal E}(G)$ for any digraph $G$, we give some lower and upper bounds of this parameter. We conclude by giving some families of digraphs having good Eulerian diameter.
Mots-clés :
Type de document :
Rapport
[Intern report] A00-R-400 || barth00a, 2000, 22 p
Domaine :

https://hal.inria.fr/inria-00099331
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:59
Dernière modification le : vendredi 12 janvier 2018 - 01:49:32

### Identifiants

• HAL Id : inria-00099331, version 1

### Citation

Dominique Barth, Pascal Berthomé, Johanne Cohen. The Eulerian stretch of a digraph and the ending guarantee of a convergence routing. [Intern report] A00-R-400 || barth00a, 2000, 22 p. 〈inria-00099331〉

### Métriques

Consultations de la notice