A framework for solving VLSI graph layout problems

DOI10.1016/0022-0000(84)90071-0zbMATH Open0543.68052OpenAlexW2029282358MaRDI QIDQ796306FDOQ796306

Sandeep Bhatt, F. Thomson Leighton

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90071-0

Recommendations

• On a graph partition problem with application to VLSI layout
• Solving Undirected Graph Problems on VLSI
• scientific article
• A graph-theoretic approach to the IC layout resizing problem
• VLSI layouts of complete graphs and star graphs
• scientific article
• The VLSI Complexity of Selected Graph Problems
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• scientific article; zbMATH DE number 3914339

zbMATH Keywords

propagation delaydivide-and-conquer framework for VLSI graph layoutfaulty processorsgraph partitioning heuristicslarge networks of processorslayout area

Mathematics Subject Classification ID

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

Cites Work

• An Efficient Heuristic Procedure for Partitioning Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universality considerations in VLSI circuits
• Title not available (Why is that?)
• New lower bound techniques for VLSI
• The complexity of minimizing wire lengths in VLSI layouts
• Title not available (Why is that?)
• Title not available (Why is that?)
• An efficient heuristic cluster algorithm for tearing large-scale networks
• Title not available (Why is that?)
• Efficient detection of determinacy races in cilk programs
• Parallel algorithms for the circuit value update problem
• Wafer-Scale Integration of Systolic Arrays
• Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees
• On driving many long wires in a VLSI layout
• A network of microprocessors to execute reduction languages, part II
• The Compilation of Regular Expressions into Integrated Circuits
• On-Line Algorithms for Path Selection in a Nonblocking Network

Cited In (only showing first 100 items - show all)

• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• Graph graphics: Theory and practice
• A branch-and-cut approach to the crossing number problem
• The MIN-cut and vertex separator problem
• Area-time tradeoffs for universal VLSI circuits
• Global wire routing in two-dimensional arrays
• The crossing number of \(K_{1,m,n}\)
• A lower bound for area-universal graphs
• On VLSI layouts of the star graph and related networks
• Crossing number and weighted crossing number of near-planar graphs
• A tighter insertion-based approximation of the crossing number
• A compact layout for the three-dimensional tree of meshes
• The Crossing Number of Graphs: Theory and Computation
• Splitting necklaces
• An exact combinatorial algorithm for minimum graph bisection
• The complexity of minimizing wire lengths in VLSI layouts
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Title not available (Why is that?)
• Title not available (Why is that?)
• Orthogonal drawings and crossing numbers of the Kronecker product of two cycles
• Title not available (Why is that?)
• The treewidth of line graphs
• New results on drawing angle graphs
• Product-shuffle networks: Toward reconciling shuffles and butterflies
• Square-root rule of two-dimensional bandwidth problem
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• Which crossing number is it anyway?
• Crossing number, pair-crossing number, and expansion
• An assignment algorithm with applications to integrated circuit layout
• The crossing number of chordal ring networks
• The complexity of tree partitioning
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• Graph layout problems
• Advances in the theory and practice of graph drawing
• Optimum embedding of complete graphs in books
• Complexities of layouts in three-dimensional VLSI circuits
• Crossing number additivity over edge cuts
• Bounding the bandwidths for graphs
• Tabu search for the cyclic bandwidth problem
• Preprocessing Steiner problems from VLSI layout
• Theory and application of width bounded geometric separators
• Lattice bandwidth of random graphs
• Modeling hypergraphs by graphs with the same mincut properties
• Algorithms for the fixed linear crossing number problem
• Exact wirelength of hypercubes on a grid
• MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
• Optimal cache-oblivious mesh layouts
• On embedding graphs in trees
• An experimental evaluation of local search heuristics for graph partitioning
• Title not available (Why is that?)
• Title not available (Why is that?)
• Min-max-boundary domain decomposition
• On the parameterized complexity of computing balanced partitions in graphs
• Embeddings of circulant networks
• Crossing-number critical graphs have bounded path-width
• Two models of two-dimensional bandwidth problems
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs
• The bisection width of cubic graphs
• Representing graph families with edge grammars
• Optimal Cheeger cuts and bisections of random geometric graphs
• Approximation Algorithms for Euler Genus and Related Problems
• Fast balanced partitioning is hard even on grids and trees
• On the crossing numbers of loop networks and generalized Petersen graphs
• Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
• New graph decompositions with applications to emulations
• Balanced partitions of trees and applications
• Representations of graphs and networks (coding, layouts and embeddings)
• Implementing shared memory on mesh-connected computers and on the fat-tree
• Rotation and crossing numbers for join products
• A fast path relinking algorithm for the min-max edge crossing problem
• Cyclic bandwidth sum of graphs
• Non-crossing shortest paths lengths in planar graphs in linear time
• UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS
• A general variable neighborhood search for the cyclic antibandwidth problem
• Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• DESIGN OF A PARALLEL INTERCONNECT BASED ON COMMUNICATION PATTERN CONSIDERATIONS
• Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge isoperimetric problems in graphs
• Vertex ordering and partitioning problems for random spatial graphs.
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• Alternative evaluation functions for the cyclic bandwidth sum problem
• Title not available (Why is that?)
• A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
• Heuristics for the constrained incremental graph drawing problem
• Real-time emulations of bounded-degree networks
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Finding minimum balanced separators -- an exact approach
• The \(S\)-\textsc{labeling} problem: an algorithmic tour
• Stochastic embeddings of graphs into trees
• Title not available (Why is that?)
• Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
• An analysis of some linear graph layout heuristics
• Exact crossing number parameterized by vertex cover
• An approach to emulating separable graphs
• Title not available (Why is that?)
• Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
• A topology-shape-metrics framework for ortho-radial graph drawing
• The crossing number of locally twisted cubes \(L T Q_n\)

This page was built for publication: A framework for solving VLSI graph layout problems

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