The Steiner tree packing problem in VLSI design

DOI10.1007/BF02614374zbMATH Open0889.90145MaRDI QIDQ1373751FDOQ1373751

Alexander Martin, Robert Weismantel, Martin Grötschel

Publication date: 22 June 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Recommendations

• Publication:3210200
• Steiner tree packing revisited
• scientific article
• Class Steiner trees and VLSI-design
• Packing Steiner trees: Polyhedral investigations
• Packing Steiner trees: Further facets
• scientific article; zbMATH DE number 2079349
• Packing Steiner trees
• Packing the Steiner trees of a graph
• Preprocessing Steiner problems from VLSI layout

zbMATH Keywords

routingVLSI designcutting planeSteiner tree packingswitchbox routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Title not available (Why is that?)
• Packing Steiner trees: A cutting plane algorithm and computational results
• Packing Steiner Trees: Separation Algorithms
• Packing Steiner trees: Polyhedral investigations
• Title not available (Why is that?)

Cited In (31)

• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• A branch-and-price algorithm for switch-box routing
• Title not available (Why is that?)
• Directed Steiner tree packing and directed tree connectivity
• Steiner tree packing revisited
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• A solution to a conjecture on the generalized connectivity of graphs
• Algorithms and Computation
• Path-connectivity of lexicographic product graphs
• Mathematical methods for physical layout of printed circuit boards: an overview
• The cavity approach for Steiner trees packing problems
• Packing the Steiner trees of a graph
• The minimum size of a graph with given tree connectivity
• Directed cycle \(k\)-connectivity of complete digraphs and complete regular bipartite digraphs
• OR Practice—Lagrangian Relaxation for Testing Infeasibility in VLSI Routing
• Heuristics for automated knowledge source integration and service composition
• Combinatorial optimization in system configuration design
• A sharp lower bound for the generalized 3-edge-connectivity of strong product graphs
• Graphs with large generalized (edge-)connectivity
• Preprocessing Steiner problems from VLSI layout
• Packing Steiner trees with identical terminal sets
• Packing strong subgraph in digraphs
• On two generalized connectivities of graphs
• Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks
• A branch-and-price algorithm for the Steiner tree packing problem.
• Hardness and approximation results for packing Steiner trees
• A PSO-based timing-driven octilinear Steiner tree algorithm for VLSI routing considering bend reduction
• On routing in VLSI design and communication networks
• Routing in grid graphs by cutting planes
• Packing trees in communication networks

Uses Software

• BEAVER

This page was built for publication: The Steiner tree packing problem in VLSI design

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