scientific article

Publication date: 23 January 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Lagrangian relaxation dynamic programming combinatorial optimization branch-and-bound layout optimization NP-hardness network flow combinatorial algorithm circuit layout detailed routing computer- aided design divide-and- conquer algorithms

Mathematics Subject Classification ID

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

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, An implicit enumeration scheme for the batch selection problem, On Turn-Regular Orthogonal Representations, Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée, Data structures for maintaining set partitions, COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗, Graph Compact Orthogonal Layout Algorithm, Efficient algorithms for minimum range cut problems, On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem, Overloaded Orthogonal Drawings, Optimal compactification of a floorplan and its relation to other optimization problems-a dynamic programming approach, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Graph Bipartization Problem with Applications to Via Minimization in VLSI Design, A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks, A local search approximation algorithm for the multiway cut problem, Visibility representations of toroidal and Klein-bottle graphs, Constrained Min-Cut Replication for K-Way Hypergraph Partitioning, New approximation results on graph matching and related problems, Parallel Candecomp/Parafac Decomposition of Sparse Tensors Using Dimension Trees, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures, A framework for solving mixed-integer semidefinite programs, PATHWIDTH AND LAYERED DRAWINGS OF TREES, Worst-case ratios of networks in the rectilinear plane, VLSI Placement Using Quadratic Programming and Network Partitioning Techniques, The DFS-heuristic for orthogonal graph drawing, On the complexity of orthogonal compaction, On the complexity of the maximum biplanar subgraph problem, Automatic layout of statecharts, A branch-and-price algorithm for the Steiner tree packing problem., Adapting Iterative-Improvement Heuristics for Scheduling File-Sharing Tasks on Heterogeneous Platforms, Some polynomially solvable subcases of the detailed routing problem in VLSI design, On triangulating planar graphs under the four-connectivity constraint, Rectangular drawings of plane graphs without designated corners, A linear algorithm for compact box-drawings of trees, SDP Relaxations for Some Combinatorial Optimization Problems, An optimal algorithm for layered wheel floorplan designs, On the approximability of time disjoint walks, Unnamed Item, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS, A spectral heuristic for bisecting random graphs, Global convergence of the alternating projection method for the Max-Cut relaxation problem, On Turn-Regular Orthogonal Representations, Finding part-machine families using graph partitioning techniques, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning