The Steiner tree packing problem in VLSI design

DOI10.1007/BF02614374zbMath0889.90145MaRDI QIDQ1373751

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)

zbMATH Keywords

VLSI designcutting planeroutingswitchbox routingSteiner tree packing

Mathematics Subject Classification ID

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

Related Items

A branch-and-price algorithm for switch-box routing, Hardness and approximation results for packing Steiner trees, Packing Steiner trees with identical terminal sets, Graphs with large generalized (edge-)connectivity, A sharp lower bound for the generalized 3-edge-connectivity of strong product graphs, Steiner tree packing revisited, Directed Steiner tree packing and directed tree connectivity, On two generalized connectivities of graphs, Packing strong subgraph in digraphs, Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs, The minimum size of a graph with given tree connectivity, The cavity approach for Steiner trees packing problems, Constructing edge-disjoint Steiner paths in lexicographic product networks, Heuristics for automated knowledge source integration and service composition, On routing in VLSI design and communication networks, A solution to a conjecture on the generalized connectivity of graphs, Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks, Packing the Steiner trees of a graph, Mathematical methods for physical layout of printed circuit boards: an overview, Path-connectivity of lexicographic product graphs, Packing trees in communication networks, Combinatorial optimization in system configuration design, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

Uses Software

• BEAVER

Cites Work

• Unnamed Item
• Unnamed Item
• Packing Steiner trees: Polyhedral investigations
• Packing Steiner trees: A cutting plane algorithm and computational results
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Packing Steiner Trees: Separation Algorithms