Upper bounds for the span in triangular lattice graphs: application to frequency planning for cellular network - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Upper bounds for the span in triangular lattice graphs: application to frequency planning for cellular network

(1) , (1)
1

Résumé

We study a problem coming from the design of wireless cellular radiocommunication network. Frequency planning constraints are modelled in terms of graph theory. For each planning function $f$ let us call $sp(f)$ - or the {\em span} of the frequency planning $f$ - the difference between the largest and the smallest frequency used. Let the {\em Order} of the graph be $Or(G)=sp(G)+1$ and the {\em maximal local order} of the graph the maximum order of a clique of $G$, i.e. $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. We show: $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$.
Ce rapport explore un problème issue de l'allocation de fréquence dans les réseaux de radiocommunication cellulaire. Le problème de planification est décrit à l'aide de la théorie des graphes. Pour une fonction donnée $f$ de plannification, on appelle le {\em span} de $f$ - ou $sp(f)$ - la différence entre la plus grande fréquence employée et la plus petite. Nous définissons aussi l'{\em ordre } du graphe comme étant $Or(G)=sp(G)+1$ et l'{\em ordre local maximum} $Mlo(G)$ comme étant l'ordre maximum d'une clique de $G$, c'est-à-dire $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. Nous montrons le résultat suivant : $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$.
Fichier principal
Vignette du fichier
RR1997-28.pdf (255.3 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102069 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102069 , version 1

Citer

Stephane Ubeda, Janez Zerovnik. Upper bounds for the span in triangular lattice graphs: application to frequency planning for cellular network. [Research Report] LIP RR-1997-28, Laboratoire de l'informatique du parallélisme. 1997, 2+15p. ⟨hal-02102069⟩
8 Consultations
20 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More