Characterization of the congestion lemma on layout computation
type: Item
instance of: scholarly article
title: Characterization of the congestion lemma on layout computation
zbMATH Open document ID: 1477.68240
DOI: 10.1155/2021/2984703
author: Jiabao Liu
author: Arul Jeya Shalini
author: Micheal Arockiaraj
author: J. Nancy Delaila
published in: Journal of Mathematics
publication date: 2021-11-24T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7433058
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2021/2984703
OpenAlex ID: W3210345926
Wikidata QID: Q124963476
cites work: Q3798268
cites work: Q4435203
cites work: Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
cites work: A framework for solving VLSI graph layout problems
cites work: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
cites work: Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees
cites work: Q4458414
cites work: Optimal Assignments of Numbers to Vertices
cites work: An edge-isoperimetric problem for powers of the Petersen graph
cites work: Exact wirelength of hypercubes on a grid
cites work: Embedding of hypercubes into sibling trees
cites work: Embeddings of circulant networks
cites work: Embedding of hypercubes into necklace, windmill and snake graphs
cites work: Q5355047
description: scientific article; zbMATH DE number 7433058