Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs (Q1084869)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs |
scientific article |
Statements
Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs (English)
0 references
1986
0 references
A direct method is devised to prove, without information-theoretic arguments, the \(\Omega (N^ 2/\log^ 2N)\) wire area lower bound for the shuffle-exchange and cube-connected cycles graphs. We further show the high occurrence of long edges in two ways: (1) In any layout, there are \(\Omega\) (N/log N) edges whose lengths are at least N/32 log\({}^ 2N\). (2) The edges whose lengths are at least N/64 log\({}^ 2N\) occupy \(\Omega (N^ 2/\log^ 2N)\) wire area.
0 references
graph layout
0 references
VLSI
0 references
wire area lower bound
0 references
long edges
0 references