Characterization of the Congestion Lemma on Layout Computation

An embedding of a guest network GN into a host network HN is to find a suitable bijective function between the vertices of the guest and the host such that each link of GN is stretched to a path in HN. The layout measure is attained by counting the length of paths in HN corresponding to the links in...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jia-Bao Liu, Arul Jeya Shalini, Micheal Arockiaraj, J. Nancy Delaila
Formato:	article
Lenguaje:	EN
Publicado:	Hindawi Limited 2021
Materias:	Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/12fe8b2e16f644a581f9346d661dca59
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:12fe8b2e16f644a581f9346d661dca59
record_format	dspace
spelling	oai:doaj.org-article:12fe8b2e16f644a581f9346d661dca592021-11-08T02:36:40ZCharacterization of the Congestion Lemma on Layout Computation2314-478510.1155/2021/2984703https://doaj.org/article/12fe8b2e16f644a581f9346d661dca592021-01-01T00:00:00Zhttp://dx.doi.org/10.1155/2021/2984703https://doaj.org/toc/2314-4785An embedding of a guest network GN into a host network HN is to find a suitable bijective function between the vertices of the guest and the host such that each link of GN is stretched to a path in HN. The layout measure is attained by counting the length of paths in HN corresponding to the links in GN and with a complexity of finding the best possible function overall graph embedding. This measure can be computed by summing the minimum congestions on each link of HN, called the congestion lemma. In the current study, we discuss and characterize the congestion lemma by considering the regularity and optimality of the guest network. The exact values of the layout are generally hard to find and were known for very restricted combinations of guest and host networks. In this series, we derive the correct layout measures of circulant networks by embedding them into the path- and cycle-of-complete graphs.Jia-Bao LiuArul Jeya ShaliniMicheal ArockiarajJ. Nancy DelailaHindawi LimitedarticleMathematicsQA1-939ENJournal of Mathematics, Vol 2021 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Mathematics QA1-939
spellingShingle	Mathematics QA1-939 Jia-Bao Liu Arul Jeya Shalini Micheal Arockiaraj J. Nancy Delaila Characterization of the Congestion Lemma on Layout Computation
description	An embedding of a guest network GN into a host network HN is to find a suitable bijective function between the vertices of the guest and the host such that each link of GN is stretched to a path in HN. The layout measure is attained by counting the length of paths in HN corresponding to the links in GN and with a complexity of finding the best possible function overall graph embedding. This measure can be computed by summing the minimum congestions on each link of HN, called the congestion lemma. In the current study, we discuss and characterize the congestion lemma by considering the regularity and optimality of the guest network. The exact values of the layout are generally hard to find and were known for very restricted combinations of guest and host networks. In this series, we derive the correct layout measures of circulant networks by embedding them into the path- and cycle-of-complete graphs.
format	article
author	Jia-Bao Liu Arul Jeya Shalini Micheal Arockiaraj J. Nancy Delaila
author_facet	Jia-Bao Liu Arul Jeya Shalini Micheal Arockiaraj J. Nancy Delaila
author_sort	Jia-Bao Liu
title	Characterization of the Congestion Lemma on Layout Computation
title_short	Characterization of the Congestion Lemma on Layout Computation
title_full	Characterization of the Congestion Lemma on Layout Computation
title_fullStr	Characterization of the Congestion Lemma on Layout Computation
title_full_unstemmed	Characterization of the Congestion Lemma on Layout Computation
title_sort	characterization of the congestion lemma on layout computation
publisher	Hindawi Limited
publishDate	2021
url	https://doaj.org/article/12fe8b2e16f644a581f9346d661dca59
work_keys_str_mv	AT jiabaoliu characterizationofthecongestionlemmaonlayoutcomputation AT aruljeyashalini characterizationofthecongestionlemmaonlayoutcomputation AT michealarockiaraj characterizationofthecongestionlemmaonlayoutcomputation AT jnancydelaila characterizationofthecongestionlemmaonlayoutcomputation
_version_	1718443066922106880

Characterization of the Congestion Lemma on Layout Computation

Ejemplares similares