scientific article
From MaRDI portal
Publication:3997942
zbMath0709.68039MaRDI QIDQ3997942
Publication date: 23 January 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lagrangian relaxationdynamic programmingcombinatorial optimizationbranch-and-boundlayout optimizationNP-hardnessnetwork flowcombinatorial algorithmcircuit layoutdetailed routingcomputer- aided designdivide-and- conquer algorithms
Programming involving graphs or networks (90C35) Combinatorics in computer science (68R05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Applications of graph theory to circuits and networks (94C15)
Related Items (only showing first 100 items - show all)
Efficient cell-based migration of VLSI layout ⋮ Dynamic programming and graph optimization problems ⋮ Approximation algorithms for multi-dimensional assignment problems with decomposable costs ⋮ Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits ⋮ The rectilinear class Steiner tree problem for intervals on two parallel lines ⋮ The pin redistribution problem in multi-chip modules ⋮ A parallel algorithm for computing Steiner trees in strongly chordal graphs ⋮ Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ Comparison of formulations and a heuristic for packing Steiner trees in a graph ⋮ Relating bends and size in orthogonal graph drawings ⋮ Self-organizing maps for drawing large graphs ⋮ HV-planarity: algorithms and complexity ⋮ A computational study of graph partitioning ⋮ On generalized greedy splitting algorithms for multiway partition problems ⋮ Monge matrices make maximization manageable ⋮ Diagonal channel routing with vias at unit distance ⋮ The number of guillotine partitions in \(d\) dimensions ⋮ Single bend wiring on surfaces ⋮ Drawing graphs on rectangular grids ⋮ Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems ⋮ A projection technique for partitioning the nodes of a graph ⋮ Unconstrained multilayer switchbox routing ⋮ The shortest multipaths problem in a capacitated dense channel ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs ⋮ Graph bisection revisited ⋮ Minimum transversals of maximum matchings as approximate solutions to the bisection problem ⋮ The Steiner tree packing problem in VLSI design ⋮ A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms ⋮ Packing Steiner trees: Polyhedral investigations ⋮ Packing Steiner trees: A cutting plane algorithm and computational results ⋮ On partitioning of hypergraphs ⋮ A better heuristic for orthogonal graph drawings ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Rectangular grid drawings of plane graphs ⋮ Steiner tree packing revisited ⋮ On the approximability of the Steiner tree problem. ⋮ An exact algorithm for graph partitioning ⋮ Spectral methods for graph bisection problems. ⋮ Approximating the bottleneck plane perfect matching of a point set ⋮ Improving graph partitions using submodular functions. ⋮ Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices ⋮ Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations ⋮ Geometric thickness in a grid ⋮ Orthogonal drawings based on the stratification of planar graphs ⋮ Semidefinite programming relaxations for the graph partitioning problem ⋮ A simple optimal binary representation of mosaic floorplans and Baxter permutations ⋮ A note on data structures for maintaining bipartitions ⋮ Modifying orthogonal drawings for label placement ⋮ On routing in VLSI design and communication networks ⋮ New algorithms for mimizing the longest wire length during circuit compaction. ⋮ A framework for 1-D compaction with forbidden region avoidance ⋮ Minimum separation for single-layer channel routing ⋮ On the parameterized complexity of layered graph drawing ⋮ A parallel algorithm to construct a dominance graph on nonoverlapping rectangles ⋮ Partitioning strategies for the block Cimmino algorithm ⋮ Area-time tradeoffs for universal VLSI circuits ⋮ Modeling hypergraphs by graphs with the same mincut properties ⋮ Complexity of pairwise shortest path routing in the grid ⋮ A better heuristic for area-compaction of orthogonal representations ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ \(k\)-spine, 1-bend planarity ⋮ Polychromatic 4-coloring of guillotine subdivisions ⋮ A Matrix Partitioning Interface to PaToH in MATLAB ⋮ Mathematical methods for physical layout of printed circuit boards: an overview ⋮ A novel formulation of the max-cut problem and related algorithm ⋮ Octagonal drawings of plane graphs with prescribed face areas ⋮ Drawing slicing graphs with face areas ⋮ The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts ⋮ Geometric quadrisection in linear time, with application to VLSI placement ⋮ Formulations and valid inequalities of the node capacitated graph partitioning problem ⋮ Switchbox routing in VLSI design: Closing the complexity gap ⋮ Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method ⋮ Insight into the computation of Steiner minimal trees in Euclidean space of general dimension ⋮ Spectral partitioning with multiple eigenvectors ⋮ Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization ⋮ A note on formulations for the \(A\)-partition problem on hypergraphs ⋮ A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis ⋮ Combinatorial optimization models for production scheduling in automated manufacturing systems ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ A new lower bound for the bipartite crossing number with applications ⋮ The node capacitated graph partitioning problem: A computational study ⋮ Solving quadratic (0,1)-problems by semidefinite programs and cutting planes ⋮ Algorithms for graph partitioning problems by means of eigenspace relaxations ⋮ Spectral bounds for graph partitioning with prescribed partition sizes ⋮ Optimal two-sided embeddings of complete binary trees in rectangular grids ⋮ A cell formation algorithm: Hypergraph approximation -- cut tree ⋮ A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation. ⋮ On the area of hypercube layouts. ⋮ The \(\gamma\)-connected assignment problem ⋮ Two-dimensional packing algorithms for layout of disconnected graphs ⋮ Graph multidimensional scaling with self-organizing maps ⋮ Well-solvable cases of the QAP with block-structured matrices ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem ⋮ The complexity of detecting crossingfree configurations in the plane ⋮ Node and edge relaxations of the max-cut problem ⋮ Best-so-far vs. where-you-are: Implications for optimal finite-time annealing ⋮ A near-optimal Manhattan channel router for a class of nets with the shift-right-one pattern
This page was built for publication:
