Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
type: Item
instance of: scholarly article
title: Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
zbMATH Open document ID: 0606.68068
DOI: 10.1016/0020-0190(86)90122-5
author: Ferng-Ching Lin
author: Wei-Kuan Shih
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
full work available at URL: 03.pdf
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 3980513
zbMATH Keywords: graph layout
zbMATH Keywords: VLSI
zbMATH Keywords: wire area lower bound
zbMATH Keywords: long edges
MaRDI profile type: Publication
OpenAlex ID: W1986286271
cites work: A framework for solving VLSI graph layout problems
cites work: An asymptotically optimal layout for the shuffle-exchange graph
cites work: New lower bound techniques for VLSI
cites work: Parallel Processing with the Perfect Shuffle
cites work: Q3326832
description: scientific article; zbMATH DE number 3980513