A framework for solving VLSI graph layout problems

DOI10.1016/0022-0000(84)90071-0zbMath0543.68052OpenAlexW2029282358MaRDI QIDQ796306

Sandeep N. Bhatt, Frank Thompson 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

zbMATH Keywords

faulty processors propagation delay divide-and-conquer framework for VLSI graph layout graph partitioning heuristics large networks of processors layout area

Mathematics Subject Classification ID

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

Related Items

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Implementing shared memory on multi-dimensional meshes and on the fat-tree ⋮ Efficient iterated greedy for the two-dimensional bandwidth minimization problem ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ A topology-shape-metrics framework for ortho-radial graph drawing ⋮ Cyclic bandwidth sum of graphs ⋮ Algorithms for the fixed linear crossing number problem ⋮ Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ A lower bound for area-universal graphs ⋮ Crossing number, pair-crossing number, and expansion ⋮ Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs ⋮ Vertex ordering and partitioning problems for random spatial graphs. ⋮ Alternative evaluation functions for the cyclic bandwidth sum problem ⋮ Heuristics for the constrained incremental graph drawing problem ⋮ The crossing number of chordal ring networks ⋮ Global wire routing in two-dimensional arrays ⋮ Splitting necklaces ⋮ $\ell ^2_2$ spreading metrics for vertex ordering problems ⋮ An approach to emulating separable graphs ⋮ Graph graphics: Theory and practice ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ On embedding graphs in trees ⋮ The $S$-\textsc{labeling} problem: an algorithmic tour ⋮ A compact layout for the three-dimensional tree of meshes ⋮ Tabu search for the cyclic bandwidth problem ⋮ The complexity of minimizing wire lengths in VLSI layouts ⋮ Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$ ⋮ Embeddings of circulant networks ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ The crossing number of locally twisted cubes $L T Q_n$ ⋮ Optimum embedding of complete graphs in books ⋮ An experimental evaluation of local search heuristics for graph partitioning ⋮ New results on drawing angle graphs ⋮ General variable neighborhood search for computing graph separators ⋮ Real-time emulations of bounded-degree networks ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ A variable depth neighborhood search algorithm for the min-max arc crossing problem ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Graph layout problems ⋮ Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength ⋮ Crossing-number critical graphs have bounded path-width ⋮ Balanced tree partition problems with virtual nodes ⋮ Theory and application of width bounded geometric separators ⋮ Optimal cache-oblivious mesh layouts ⋮ A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout ⋮ Orthogonal drawings and crossing numbers of the Kronecker product of two cycles ⋮ Optimal Embedding of Locally Twisted Cubes into Grids ⋮ Exact crossing number parameterized by vertex cover ⋮ É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 ⋮ Rotation and crossing numbers for join products ⋮ Crossing number additivity over edge cuts ⋮ A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints ⋮ Orthogonal drawings of graphs for the automation of VLSI circuit design ⋮ Two models of two-dimensional bandwidth problems ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ New graph decompositions with applications to emulations ⋮ A branch-and-cut approach to the crossing number problem ⋮ The MIN-cut and vertex separator problem ⋮ Product-shuffle networks: Toward reconciling shuffles and butterflies ⋮ A hybrid breakout local search and reinforcement learning approach to the vertex separator problem ⋮ Area-time tradeoffs for universal VLSI circuits ⋮ DESIGN OF A PARALLEL INTERCONNECT BASED ON COMMUNICATION PATTERN CONSIDERATIONS ⋮ A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs ⋮ Modeling hypergraphs by graphs with the same mincut properties ⋮ Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge isoperimetric problems in graphs ⋮ Crossing number and weighted crossing number of near-planar graphs ⋮ A tighter insertion-based approximation of the crossing number ⋮ An analysis of some linear graph layout heuristics ⋮ Min-max-boundary domain decomposition ⋮ The treewidth of line graphs ⋮ MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING ⋮ Crossing and Weighted Crossing Number of Near-Planar Graphs ⋮ The crossing number of $K_{1,m,n}$ ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Representing graph families with edge grammars ⋮ Unnamed Item ⋮ The complexity of tree partitioning ⋮ Characterization of the congestion lemma on layout computation ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ A note on the crossing number of the cone of a graph ⋮ UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS ⋮ Complexities of layouts in three-dimensional VLSI circuits ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ Exact wirelength of hypercubes on a grid ⋮ Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design ⋮ Embedding algorithm of spined cube into grid structure and its wirelength computation ⋮ The bisection width of cubic graphs ⋮ Advances in the theory and practice of graph drawing ⋮ A new lower bound for the bipartite crossing number with applications ⋮ Square-root rule of two-dimensional bandwidth problem ⋮ Bounding the bandwidths for graphs ⋮ On the complexity of planar Boolean circuits ⋮ Tabu search for min-max edge crossing in graphs ⋮ On the crossing numbers of loop networks and generalized Petersen graphs ⋮ Which crossing number is it anyway? ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ Implementing shared memory on mesh-connected computers and on the fat-tree ⋮ Self-adjusting grid networks to minimize expected path length ⋮ Balanced partitions of trees and applications ⋮ An upper bound for the crossing number of augmented cubes ⋮ Self-adjusting Grid Networks to Minimize Expected Path Length ⋮ Lattice bandwidth of random graphs ⋮ A general variable neighborhood search for the cyclic antibandwidth problem

Cites Work