Título:
Optimal edge fault-tolerant embedding of a star over a cycle.
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Akagi, Tadashi
Canale, Eduardo A.
Risso, Claudio E.
Canale, Eduardo A.
Risso, Claudio E.
Tutor:
Tipo de documento:
Artículo
Editor:
Palabras clave:
Embeddings
Multilayer Networks
Routing
Multilayer Networks
Routing
Descriptores:
Año de publicación:
2017
Contenido:
Resumen:
An embedding of a guest graph G over a host graph H is an injective map Φ from the vertices of G to the vertices of H and a mapping ρ, which associates every edge e = {x, y} in G to a Φ(x)-Φ(y) path ρ(e) in H. Given an edge f in H, if ρ−1 is the set of those edges that cross f, i.e., {e : f ∈ ρ(e)}, then the cardinality of ρ−1(f) is the (edge) congestion congρ(f) of f. The length of ρ(e) is called the dilatation dil(e) of e. The sum of all the dilatations is the
cost of the embedding. The removal of an edge f of H gives rise to a surviving graph Gf = G\ρ−1(f). Given positive integers n and b, and a fixed vertex v of the n-cycle Cn, we are facing the problem of finding a guest graph G of n vertices with an embedding (Φ, ρ) over Cn of minimum cost, such that for any surviving graph Gf there is
an embedding of the star Sn = K1,n−1 over Gf that associates the center of the star to Φ−1(v), with congestions not greater than b. This work presents the optimal cost as well as a family of optimal solutions.
Descripción:
Vol. 45 – 2017 – 7th Latin-American Workshop on Cliques in Graphs.
metadata.articulos.dc.description.uri:
Editorial:
Sociedade Brasileira de Matemática
EN:
Matemática Contemporânea, vol. 45, 2017, pp. 115-123.
Financiadores:
Financiado parcialmente por PEDECIBA-Informática (Uruguay) y por el proyecto STIC-AMSUD 15STIC-07 DAT (proyecto conjunto Chile-Francia-Uruguay).
Citación:
Akagi, T., Canale, E. y Risso, C. "Optimal edge fault-tolerant embedding of a star over a cycle". Matemática Contemporânea. [en línea]. 2017, vol. 45, pp. 115-123. DOI: 10.21711/231766362017/rmc4513.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
2317-6636
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| ACR17.pdf | Versión publicada | 461.39 KB | Adobe PDF |