A lower bound on the area of permutation layouts

DOI10.1007/BF01759044zbMath0711.68054OpenAlexW2016506329MaRDI QIDQ922710

Nathan Linial, David Lichtenstein, Avi Wigderson, Alok Aggarwal, Maria M. Klawe

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

permutationlower boundVLSIlayoutgrid embeddingmultilayer grids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Related Items

Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI, Multilayer grid embeddings for VLSI, A partial k-arboretum of graphs with bounded treewidth, Shallow grates

Cites Work

• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Multilayer grid embeddings for VLSI
• Expanding graphs contain all small trees
• Explicit construction of linear sized tolerant networks
• Ramanujan graphs
• Eigenvalues and expanders
• Universal Chains and Wiring Layouts
• A Separator Theorem for Planar Graphs
• Universality considerations in VLSI circuits
• Applications of a Planar Separator Theorem
• New lower bound techniques for VLSI
• Double-row planar routing and permutation layout
• Thickness of graphs with degree constrained vertices
• The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer case
• Permutation layout
• On optimum single-row routing
• Optimal Rearrangeable Multistage Connecting Networks