New lower bound techniques for VLSI

DOI10.1007/BF01744433MaRDI QIDQ3950484zbMATH OpenOpenAlexFDO

Authors F. Thomson Leighton

Publication date 1984

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01744433

zbMATH Keywords

area-efficient chip layoutsbisection widthcrossing numbergraph embeddinglayout areamaximum edge lengthmesh of treesN-node planar graphparallel computationseparatorThompson grid modeltree of meshesvery large scale integrationwire areawire length

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Cites work

• A model of computation for VLSI with related complexity results
• Applications of a Planar Separator Theorem
• Area-time optimal VLSI networks for multiplying matrices
• Bounds to Complexities of Networks for Sorting and for Switching
• scientific article; zbMATH DE number 3821102 (Why is no real title available?)
• The crossing number of K5,n
• The VLSI Complexity of Sorting
• Universality considerations in VLSI circuits

Cited in

(47)

• On edges crossing few other edges in simple topological complete graphs
• Extremal problems on triangle areas in two and three dimensions
• Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
• A compact layout for the three-dimensional tree of meshes
• Representations of graphs and networks (coding, layouts and embeddings)
• Parallel restructuring and evaluation of expressions
• Shallow grates
• The crossing number of locally twisted cubes \(L T Q_n\)
• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• On the \(k\)-planar local crossing number
• An asymptotically optimal layout for the shuffle-exchange graph
• Which crossing number is it anyway?
• Crossing number, pair-crossing number, and expansion
• Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
• Testing gap \(k\)-planarity is NP-complete
• Crossing lemma for the odd-crossing number
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• Feedback vertex sets in mesh-based networks
• On the decay of crossing numbers
• An upper bound for the crossing number of augmented cubes
• Space crossing numbers
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Crossing numbers of random graphs
• Representing shared data on distributed-memory parallel computers
• A survey of graphs with known or bounded crossing numbers
• Simultaneous arithmetic progressions on algebraic curves
• Applications of a new separator theorem for string graphs
• A Bipartite Strengthening of the Crossing Lemma
• Graph theory (algorithmic, algebraic, and metric problems)
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• String graphs and incomparability graphs
• Non-crossing shortest paths lengths in planar graphs in linear time
• From art and circuit design to geometry and combinatorics
• An annotated review on graph drawing and its applications
• Non-crossing shortest paths lengths in planar graphs in linear time
• The crossing number of Cartesian product of sunlet graph with path and complete bipartite graph
• The Dirac-Goodman-Pollack conjecture
• Rectilinear crossing number of graphs excluding a single-crossing graph as a minor
• 1-planar unit distance graphs
• 1-planar unit distance graphs
• Complexities of layouts in three-dimensional VLSI circuits
• Deterministic P-RAM simulation with constant redundancy
• A framework for solving VLSI graph layout problems
• Multilayer grid embeddings for VLSI
• A lower bound on the area of permutation layouts
• A bipartite strengthening of the crossing Lemma

This page was built for publication: New lower bound techniques for VLSI

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3950484)