Congestion and dilation, similarities and differences: A survey.
André Raspaud, Ondřej Sýkora, Imrich Vrt’o · 2000
We survey general results on congestion and dilation, and their special cases (cyclic) cutwidth and (cyclic) bandwidth, with the emphasis on the similarity and the duality of both parameters. Keywords Bandwidth, Congestion, Cutwidth, Embedding, Dilation 1 Introduction Recently diverse properties and invariants of interconnection networks (not only those of parallel machines) have been studied and a lot of interesting results have been shown (e.g. see [16, 36]). One of the important features of an interconnection network is its ability to efficiently simulate programs written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding. Informally, the graph embedding problem is to label the vertices of a "guest" graph (e.g. a communication graph of processes and relations between the processes) G by distinct vertices of a "host" graph (an interconnection network) H. The quality of the embedding corresponding to the efficiency of the sim...