CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven a graph $G=(V,E)$ and two positive integers $j$ and $k$, an $L(j,k)$-edge-labeling is a function $f$ assigning to edges of $E$ colors from a set ${ 0, 1, ldots , k_f }$ such that $|f(e)-f(e')| geq j$ if $e$ and $e'$ are adjacent, i.e. they share a common endpoint, $|f(e)-f(e')| geq k$ if $e$ and $e'$ are not adjacent and there exists an edge adjacent to both $e$ and $e'$. The aim of the $L(j,k)$-edge-labeling problem consists of finding a coloring function $f$ such that the value of $k_f$ is minimum. This minimum value is called $lambda'_{j,k}(G)$. This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on $lambda'_{j,k}$ have been proposed. In this paper we close some of these gaps or find better bounds on $lambda'_{j,k}$ in the special cases $j=1,2$ and $k=1$. Moreover, we propose tight $L(j,k)$-edge-labelings for eight-regular grids.
Optimal L(j, k)-Edge-Labeling of Regular Grids / Calamoneri, Tiziana. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - STAMPA. - 4:26(2015), pp. 523-535.
| Titolo: | Optimal L(j, k)-Edge-Labeling of Regular Grids |
| Autori: | |
| Data di pubblicazione: | 2015 |
| Rivista: | |
| Citazione: | Optimal L(j, k)-Edge-Labeling of Regular Grids / Calamoneri, Tiziana. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - STAMPA. - 4:26(2015), pp. 523-535. |
| Handle: | http://hdl.handle.net/11573/779510 |
| Appartiene alla tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
| File | Note | Tipologia | Licenza | |
|---|---|---|---|---|
| Calamoneri_optimal_2015.pdf | Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione) | Tutti i diritti riservati (All rights reserved) | Administrator Richiedi una copia |
http://hdl.handle.net/11573/779510
Copyright © 2020