B. ZERROUK, S. TRICOT, B. ROTTEMBOURG Proper Linear Interval Routing Schemes L'étiquettage par intervalle est une solution intéressante pour l'implémentation de tables de routage compactes dans un réseau d'interconnexion à passage de messages L'étiquettage linéaire est une sous classe dans ce type de schéma. Dans cet article, nous nous intéressons à un étiquettage linéaire propre sur des graphes non pondérés. Un étiquettage propre est tel qu' une étiquette associée à un noeud donné n'appartient à aucun des intervalles associés aux sorties de ce noeud. Nous donnons des condition nécessaires définissant ainsi une classe de graphes qui semble familiaire. Le but de ce papier est d'ouvrir le problème suivant : est-ce que la classe de graphes ayant un étiquettage linéaire propre est parfaite, dans le sens où chaque graphe de cette classe est con­ structible moyennant des opérateurs simple, et qu'il possède un schéma de routage propre optimal qui est formellement non blo­ quant ? Interval labeling is interesting for the implemen­ tation of compact routing tables in message passing interconnex­ ion networks. Linear interval labeling is a subclass in the in­ terval labeling hierarchy. In this paper we consider a proper linear interval labeling on unweighted graphs. A proper interval labeling is a linear interval labeling such that a label of any node is not contained in any interval of an outgoing link of that node. We give necessary conditions for which a graph may admit a proper linear interval scheme. We show that the class of those graphs includes familiar structures. The aim of this paper is to open the problem that the class of graphs which admit optimal proper linear interval schemes defines an "ideal" class of topologies : any topology of this class is constructible and has an optimal deadlock-free routing function. Constructibility means that any topology of this class can be well described using simple graph operators (or operations).