An L(1, 1)-coloring of the n-dimensional hypercube Qn assigns nodes of Qn which are at distance ≤ 2 with different colors. Such colorings find application, e.g., in frequency assignment in wireless networks and data distribution in parallel memory systems. Let Χ 2̄(Qn) be the minimum number of colors used in any L(1, 1)-coloring. Finding the exact value of Χ2̄(Q n) is still an. open problem, and only 2-approximate solutions are currently known. In this paper we expose some connections between group theory and the L(1, 1)-coloring problem. Namely, we unfold the algebraic structure on which the best available L(1, 1)-coloring algorithms of Qn are based, thus giving a group theoretic flavour to existing L(1, 1)-colorings. We show that identifying groups such that the inverse of each element is the element itself yields a simple and efficient way to obtain L(1, 1)-colorings of the hypercube. We also prove that such colorings are balanced and that every coloring algorithm based on this algebraic structure cannot improve the current upper bound on Χ2̄(Qn), independently of the choice of the group operation. © 2008 IEEE.

A Note on Algebraic Hypercube Colorings / FINOCCHI, Irene; FUSCO, EMANUELE GUIDO; PETRESCHI, Rossella. - STAMPA. - (2008), pp. 869-874. ((Intervento presentato al convegno Information Technology : New Generations tenutosi a Las Vegas; United States nel 7 - 9 April 2008 [10.1109/itng.2008.173].

A Note on Algebraic Hypercube Colorings

FINOCCHI, Irene;FUSCO, EMANUELE GUIDO;PETRESCHI, Rossella
2008

Abstract

An L(1, 1)-coloring of the n-dimensional hypercube Qn assigns nodes of Qn which are at distance ≤ 2 with different colors. Such colorings find application, e.g., in frequency assignment in wireless networks and data distribution in parallel memory systems. Let Χ 2̄(Qn) be the minimum number of colors used in any L(1, 1)-coloring. Finding the exact value of Χ2̄(Q n) is still an. open problem, and only 2-approximate solutions are currently known. In this paper we expose some connections between group theory and the L(1, 1)-coloring problem. Namely, we unfold the algebraic structure on which the best available L(1, 1)-coloring algorithms of Qn are based, thus giving a group theoretic flavour to existing L(1, 1)-colorings. We show that identifying groups such that the inverse of each element is the element itself yields a simple and efficient way to obtain L(1, 1)-colorings of the hypercube. We also prove that such colorings are balanced and that every coloring algorithm based on this algebraic structure cannot improve the current upper bound on Χ2̄(Qn), independently of the choice of the group operation. © 2008 IEEE.
9780769530994
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/367690
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact