HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

Dominique Barth 1 Pascal Berthomé 2 Johanne Cohen 3
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.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:52:59 AM
Last modification on : Thursday, January 20, 2022 - 5:32:09 PM


  • HAL Id : inria-00099331, version 1


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⟩



Record views