Logo image
Back
Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
Journal article   Peer reviewed

Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs

Ferng-Ching Lin and Wei-Kuan Shih
Information Processing Letters, Vol.23(1), pp.5-9
20/07/1986
DOI: https://doi.org/10.1016/0020-0190(86)90122-5

Abstract

communication power of edge cube-connected cycles Graph layout long edges lower bound path-edge shuffle-exchange VLSI wire area
A direct method is devised to prove, without information-theoretic arguments, the Ω(N 2 /log 2 N) 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 Ω(N/log N) edges whose lengths are at least N/32 log 2 N. (2) The edges whose lengths are at least N/64 log 2 N occupy Ω(N 2 /log 2 N) wire area. © 1986.

Metrics

1 Record Views

Details

Logo image