Packing Steiner trees: a cutting plane algorithm and computational results

1. J.F. Benders, “Partitioning procedures for solving mixed-variables programming problems,”Numerische Mathematik 4 (1962) 238–252.

   Article  MATH  MathSciNet  Google Scholar 

2. M.L. Brady and D.J. Brown, “VLSI routing: Four layers suffice,” in: F.P. Preparata, ed.,Advances in Computing Research. Vol. 2: VLSI Theory (Jai Press, London, 1984) pp. 245–258.

   Google Scholar 

3. M. Burstein and R. Pelavin, “Hierarchical wire routing,”IEEE Transactions on Computer-Aided-Design CAD-2 (1983) 223–234.

   Article  Google Scholar 

4. J.P. Cohoon and P.L. Heck, “BEAVER: A computational-geometry-based tool for switchbox routing,”IEEE Transactions on Computer-Aided-Design CAD-7 (1988) 684–697.

   Article  Google Scholar 

5. G.B. Dantzig and P. Wolfe, “Decomposition principle for linear programs,”Operations Research 8 (1960) 101–111.

   MATH  Google Scholar 

6. S.E. Dreyfus and R.A. Wagner, “The Steiner problem in graphs,”Networks 1 (1971) 195–207.

   MathSciNet  Google Scholar 

7. R.E. Erickson, C.L. Monma and A.F. Veinott, “Send-and-split method for minimum concave-cost network flows,”Mathematics of Operations Research 12 (1987) 634–664.

   MATH  MathSciNet  Google Scholar 

8. M.R. Garey and D.S. Johnson, “The rectilinear Steiner tree problem is-complete,”SIAM Journal on Applied Mathematics 32 (1977) 826–834.

   Article  MATH  MathSciNet  Google Scholar 

9. M. Grötschel and O. Holland, “Solution of large-scale symmetric travelling salesman problems,”Mathematical Programming 51 (1991) 141–202.

   Article  MATH  MathSciNet  Google Scholar 

10. M. Grötschel, A. Martin and R. Weismantel, “Routing in Grid Graphs by Cutting Planes,”Zeitschrift für Operations Research 41 (1995) 255–275.

    MATH  Google Scholar 

11. M. Grötschel, A. Martin and R. Weismantel, “Packing Steiner trees: separation algorithms,”SIAM Journal on Discrete Mathematics, to appear.

12. M. Grötschel, A. Martin and R. Weismantel, “Packing Steiner trees: polyhedral investigations,” Mathematical Programming 72 (1996) (this issue).

13. M. Grötschel and C.L. Monma, “Integer polyhedra associated with certain network design problems with connectivity constraints,”SIAM Journal on Discrete Mathematics 3 (1990) 502–523.

    Article  MATH  MathSciNet  Google Scholar 

14. M. Grötschel, C.L. Monma and M. Stoer, “Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints,”Operations Research 40 (1992) 309–330.

    Article  MATH  MathSciNet  Google Scholar 

15. R.M. Karp, “Reducibility among combinational problems,” in: R.E. Miller and J.W. Thatcher, eds.,Complexity of Computer Computations (Plenum, New York, 1972) pp. 85–103.

    Google Scholar 

16. M.R. Kramer and J. van Leeuwen, “The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits,” in: F.P. Preparata, ed.,Advances in Computing Research, Vol. 2: VSLI Theory (Jai Press, London, 1984) pp. 129–146.

    Google Scholar 

17. T. Lengauer,Combinatorial Algorithms for Integrated Circuit Layout (Wiley, Chichester, 1990).

    MATH  Google Scholar 

18. W. Lipski, “On the structure of three-layer wireable layouts,” in: F.P. Preparata, ed.,Advances in Computing Research, Vol. 2: VLSI Theory (Jai Press, London, 1984) pp. 231–244.

    Google Scholar 

19. W.K. Luk, “A greedy switch-box router,”Integration 3 (1985) 129–149.

    Google Scholar 

20. A. Martin, “Packen von Steinerbäumen: Polyedrische Studien und Anwendung,” Ph.D. Thesis, Technische Universität Berlin, (1992).

21. M. Padberg and G. Rinaldi, “A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems,”SIAM Review 33 (1991) 60–100.

    Article  MATH  MathSciNet  Google Scholar 

22. M. Sarrafzadeh, “Channel-routing problem in the knock-knee mode is-complete,”IEEE Transactions on Computer-Aided-Design CAD-6 (1987) 503–506.

    Article  Google Scholar 

Download references