ganley.org -> The Steiner Tree Page -> Bibliography

Bibliography

Generated from steiner.bib by bib2html.

P. K. Agarwal and M. I. Shing. Algorithms for the special cases of rectilinear Steiner trees: I. Points on the boundary of a rectilinear rectangle. Networks, 20:453-485, 1990.
A. V. Aho, M. R. Garey, and F. K. Hwang. Rectilinear Steiner trees: Efficient special-case algorithms. Networks, 7:37-58, 1977.
M. J. Alexander and G. Robins. A new approach to FPGA routing based on multi-weighted graphs. In Proceedings of the International Workshop on Field-Programmable Gate Arrays, 1994.
M. J. Alexander, J. P. Cohoon, J. L. Ganley, and G. Robins. An architecture-independent approach to FPGA routing based on multi-weighted graphs. In Proceedings of the European Design Automation Conference, pages 259-264, 1994. (PostScript)
M. J. Alexander, J. P. Cohoon, J. L. Ganley, and G. Robins. Performance-oriented placement and routing for field-programmable gate arrays. In Proceedings of the European Design Automation Conference, pages 80-85, 1995. (PostScript)
B. Aronov, M. Bern, and D. Eppstein. On the number of minimal 1-Steiner trees. Discrete and Computational Geometry, pages 29-34, 1994.
S. Arora. Polynomial-time approximation scheme for Euclidean TSP and other geometric problems. In Proceedings of the Symposium on Foundations of Computer Science, pages 2-11, 1996.
PTAS for Euclidean and rectilinear Steiner trees
H. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, Reading, Massachusetts, 1990.
S. Bapat and J. P. Cohoon. A parallel VLSI circuit layout methodology. In Proceedings of the Sixth International Conference on VLSI Design, pages 236-241, 1993.
S. Bapat, J. P. Cohoon, P. L. Heck, A. Ju, and L. J. Randall. Examining routing solutions. In Proceedings of the Second Great Lakes Symposium on VLSI, February 1992.
S. Bapat. A sharp methodology for VLSI layout. PhD thesis, Department of Computer Science, University of Virginia, Charlottesville, Virginia, 1993.
T. Barrerra, J. Griffith, S. A. McKee, G. Robins, and T. Zhang. Toward a Steiner engine: Enhanced serial and parallel implementations of the iterated 1-Steiner MRST heuristic. In Proceedings of the Third Great Lakes Symposium on VLSI, pages 90-94, 1992.
J. E. Beasley. An SST-based algorithm for the Steiner problem in graphs. Networks, 19:1-16, 1989.
J. E. Beasley. A heuristic for Euclidean and rectilinear Steiner problems. European Journal of Operational Research, 58:284-292, 1992.
P. Berman and V. Ramaiyer. Improved approximations for the Steiner tree problem. In Proceedings of the Third Symposium on Discrete Algorithms, pages 325-334, 1992.
P. Berman and V. Ramaiyer. Improved approximations for the Steiner tree problem. Journal of Algorithms, 17:381-408, 1994.
M. W. Bern. Two probabilistic results on rectilinear Steiner trees. Algorithmica, 3:191-204, 1988.
M. Bern. Faster exact algorithms for Steiner trees in planar networks. Networks, 20:109-120, 1990.
K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins. Fidelity and near-optimality of Elmore-based routing constructions. In Proceedings of the International Conference on Computer Design, pages 182-187, 1993. (PostScript)
K. D. Boese, A. B. Kahng, and G. Robins. High-performance routing trees with identified critical sinks. In Proceedings of the Thirtieth Design Automation Conference, pages 182-187, 1993. (PostScript)
K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins. Rectilinear Steiner trees with minimum Elmore delay. In Proceeedings of the Design Automation Conference, pages 381-386, 1994. (PostScript)
K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins. Near-optimal critical sink routing tree constructions. IEEE Transactions on Computer-Aided Design, pages 1417-1436, 1995. (PostScript)
R. S. Booth. Analytic formulas for full Steiner trees. Discrete and Computational Geometry, 6:69-82, 1991.
A. Borchers and D.-Z. Du. The k-Steiner ratio in graphs. SIAM Journal on Computing, 26:857-869, 1997.
Derives the Steiner ratio for k-restricted Steiner trees in graphs, i.e. those in which no full tree contains more than k terminals.
W. M. Boyce and J. E. Seery. STEINER 72: An improved version of Cockayne and Schiller's program STEINER for the minimal network problem. Technical Report 35, Bell Laboratories, Murray Hill, New Jersey, 1973.
W. M. Boyce. An improved program for the full Steiner tree problem. ACM Transactions on Mathematical Software, 3:359-385, 1977.
M. Brazil, T. Cole, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald. Minimal steiner trees for 2^k times 2^k square lattices. Journal of Combinatorial Theory, Series A, 72, 1995.
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald. Full minimal steiner trees on lattice sets. Technical Report 14-1995, Department of Mathematics, University of Melbourne, Victoria, Australia, 1995.
T. Chao and Y. Hsu. Rectilinear Steiner tree construction by local and global refinement. In Proceedings of the International Conference on Computer-Aided Design, pages 432-435, 1990.
D. S. Chen. Constrained wirelength minimization of a Steiner tree. Technical report, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois, 1994.
S. Cheng, A. Lim, and C. Wu. Optimal rectilinear Steiner tree for extremal point sets. Technical Report HKUST-CS93-6, Department of Computer Science, Hong Kong University of Science and Technology, Kowloon, Hong Kong, April 1993.
S. Cheng, A. Lim, and C. Wu. Optimal rectilinear Steiner tree for extremal point sets. In Proceedings of the International Symposium on Algorithms and Computation, volume 762 of Lecture Notes in Computer Science, pages 523-532. Springer-Verlag, Berlin, Germany, 1993.
C. Chiang, M. Sarrafzadeh, and C. K. Wong. Global routing based on Steiner min-max trees. IEEE Transactions on Computer-Aided Design, 9:1318-1325, 1990.
C. Chiang, M. Sarrafzadeh, and C. K. Wong. An optimal algorithm for rectilinear Steiner trees for channels with obstacles. International Journal of Circuit Theory and Applications, 19:551-563, 1991.
C. Chiang, M. Sarrafzadeh, and C. K. Wong. An algorithm for exact rectilinear Steiner trees for switchbox with obstacles. IEEE Transactions on Circuits and Systems, 39:446-455, 1992.
C. Chiang, C. K. Wong, and M. Sarrafzadeh. A weighted Steiner tree-based global router with simultaneous length and density minimization. IEEE Transactions on Computer-Aided Design, pages 1461-1469, 1994.
J.-D. Cho. A min-cost flow base min-cost rectilinear Steiner distance-preserving tree construction. In Proceedings of the International Symposium on Physical Design, pages 82-87, 1997.
S. Chopra and M. R. Rao. The Steiner tree problem 1: Formulations, compositions, and extension of facets. Mathematical Programming, 64:209-229, 1994.
S. Chopra and M. R. Rao. The Steiner tree problem 2: Properties and classes of facets. Mathematical Programming, 64:231-246, 1994.
F. R. K. Chung and R. L. Graham. Steiner trees for ladders. Annals of Discrete Mathematics, 2:173-200, 1978.
F. R. K. Chung and F. K. Hwang. A lower bound for the Steiner tree problem. SIAM Journal on Applied Mathematics, 34:27-36, 1978.
F. R. K. Chung and F. K. Hwang. The largest minimal rectilinear Steiner trees for a set of n points enclosed in a rectangle with given perimeter. Networks, 9:19-36, 1979.
F. R. K. Chung, M. Gardner, and R. L. Graham. Steiner trees on a checkerboard. Mathematics Magazine, 62:83-96, 1989.
J. Cloutier and I. Bennour. Topological characterization of Hwang's optimal Steiner trees. In Proceedings of the Canadian Conference on Computational Geometry, pages 157-162, 1993.
E. J. Cockayne and D. E. Hewgill. Exact computation of Steiner minimal trees in the plane. Information Processing Letters, 22:151-156, 1986.
E. J. Cockayne and D. E. Hewgill. Improved computation of plane Steiner minimal trees. Algorithmica, 7:219-229, 1992.
E. J. Cockayne. On the Steiner problem. Canadian Mathematical Bulletin, 10:431-450, 1967.
J. P. Cohoon and J. L. Ganley. Rectilinear interconnections in the presence of obstacles. In Y. T. Wong and M. Pecht, editors, Advanced Routing of Electronic Modules. CRC Press, Boca Raton, Florida, 1996.
J. P. Cohoon and J. L. Ganley. Rectilinear Steiner trees on a checkerboard. ACM Transactions on Design Automation of Electronic Systems, 1, 1996. (PostScript) (PDF)
A full-set decomposition algorithm and other results for rectilinear Steiner trees of terminals from a small integer grid
J. P. Cohoon, D. S. Richards, and J. S. Salowe. An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of a rectangle. IEEE Transactions on Computer-Aided Design, 9:398-407, 1990.
J. Cong, K. S. Leung, and D. Zhou. Performance-driven interconnect design based on distributed RC delay model. In Proceedings of the Thirtieth Design Automation Conference, pages 606-611, 1993.
J. Córdova and Y.-H. Lee. A heuristic algorithm for the rectilinear Steiner arborescence problem. Technical Report TR-94-025, Computer and Information Sciences Department, University of Florida, Gainesville, Florida, August 1994.
P. M. Dearing and R. L. Francis. A network flow solution to a multifacility location problem involving rectilinear distances. Transportation Science, 8:126-141, 1974.
L. L. Deneen and J. B. Dezell. Using partitioning and clustering techniques to generate rectilinear Steiner trees. In Proceedings of the Second Canadian Conference on Computational Geometry, pages 315-318, 1990.
L. L. Deneen, G. M. Shute, and C. D. Thomborson. A probably fast, provably optimal algorithm for rectilinear Steiner trees. Random Structures and Algorithms, 5:535-557, 1994.
S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195-207, 1972.
Z. Drezner and G. O. Wesolowsky. Layout of facilities with some fixed points. Computers and Operations Research, 12:603-610, 1985.
D. Z. Du and F. K. Hwang. A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica, 7:121-135, 1992.
C. W. Duin. Steiner's problem in graphs: Approximation, reduction, estimation. PhD thesis, Faculteit der Economische Wetenschappen en Econometrie, Universiteit von Amsterdam, Amsterdam, The Netherlands, 1993.
J. Elzinga, D. Hearn, and W. D. Randolph. Minimax multifacility location with Euclidean distances. Transportation Science, 10:321-336, 1976.
R. E. Erickson, C. L. Monma, and A. F. Veinott Jr. Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research, 12:634-664, 1987.
J. W. Eyster and J. A. White. Some properties of the squared Euclidean distance location problem. AIIE Transactions, 5:275-280, 1973.
U. Fößmeier and M. Kaufmann. Solving rectilinear Steiner tree problems exactly in theory and practice. In Proceedings of the European Symposium on Algorithms, 1997. (PostScript)
U. Fößmeier, M. Kaufmann, and A. Z. Zelikovsky. Faster approximation algorithms for the rectilinear Steiner tree problem. In Proceedings of the 4th Annual International Symposium on Algorithms and Computation, volume ?? of Lecture Notes in Computer Science, page ?? Springer-Verlag, 1993.
R. L. Francis and J. A. White. Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
R. L. Francis, L. F. McGinnis, and J. A. White. Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs, New Jersey, 1992.
J. L. Ganley and J. P. Cohoon. A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees. In Proceedings of the Fourth Great Lakes Symposium on VLSI, pages 238-241, 1994.
An O(n 3^n) algorithm for computing optimal rectilinear Steiner trees
J. L. Ganley and J. P. Cohoon. Optimal rectilinear Steiner minimal trees in O(n² 2.62ⁿ) time. In Proceedings of the Sixth Canadian Conference on Computational Geometry, pages 308-313, 1994.
An O(n^2 2.62^n) algorithm for computing optimal rectilinear Steiner trees
J. L. Ganley and J. P. Cohoon. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In Proceedings of the International Symposium on Circuits and Systems, pages 113-116, 1994.
Proves an analogue of Hanan's theorem for rectilinear Steiner trees in the presence of obstacles, and some related results
J. L. Ganley and J. P. Cohoon. Thumbnail rectilinear Steiner trees. In Proceedings of the Fifth Great Lakes Symposium on VLSI, pages 46-49, 1995.
A full-set decomposition algorithm and other results for rectilinear Steiner trees of terminals from a small integer grid
J. L. Ganley and J. P. Cohoon. Improved computation of optimal rectilinear steiner minimal trees. International Journal of Computational Geometry and Applications, 1997. (to appear).
An O(n 3^n) algorithm and an O(n^2 2.62^n) algorithm for computing optimal rectilinear Steiner trees
J. L. Ganley and J. S. Salowe. Optimal and approximate bottleneck Steiner trees. Operations Research Letters, 19:217-224, 1996.
An exact algorithm for Euclidean Steiner trees that minimize the length of the longest edge, and the value of the corresponding version of the Steiner ratio
J. L. Ganley. Geometric Interconnection and Placement Algorithms. PhD thesis, Department of Computer Science, University of Virginia, Charlottesville, Virginia, 1995. (PostScript) (PDF)
M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32:826-834, 1977.
M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 32:835-859, 1977.
Proves that the Euclidean Steiner tree problem is NP-hard
G. Georgakopoulos and C. H. Papadimitriou. The 1-Steiner tree problem. Journal of Algorithms, 8:122-130, 1987.
E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16:1-29, 1966.
M. X. Goemans and Y. S. Myung. A catalog of Steiner tree formulations. Networks, 23:19-28, 1993.
M. X. Goemans. The Steiner tree polytope and related polyhedra. Mathematical Programming, 63:157-182, 1994.
G. R. Grimwood. The Euclidean Steiner tree problem: Simulated annealing and other heuristics. Master's thesis, Victoria University, Wellington, New Zealand, 1994.
M. Grötschel, A. Martin, and R. Weismantel. Packing Steiner trees: A cutting plane algorithm and computational results. Mathematical Programming, 72:125-145, 1996.
M. Grötschel, A. Martin, and R. Weismantel. Packing Steiner trees: Polyhedral investigations. Mathematical Programming, 72:101-123, 1996.
T. Akama H. Suzuki and T. Nishizeki. Finding Steiner forests in planar graphs. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 444-453, 1990.
S. L. Hakimi. Steiner's problem in graphs and its implications. Networks, 1:113-133, 1971.
M. Hanan. On Steiner's problem with rectilinear distance. SIAM Journal on Applied Mathematics, 14:255-265, 1966.
N. Hasan, G. Vijayan, and C. K. Wong. A neighborhood improvement algorithm for rectilinear Steiner trees. In Proceedings of the International Symposium on Circuits and Systems, pages 2869-2872, 1990.
Hesser, Manner, and Stucky. Optimisation of Steiner trees using genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, 1989.
D. W. Hightower. The interconnection problem--a tutorial. In Proceedings of the Tenth Design Automation Workshop, pages 1-21, 1973.
J. Ho, G. Vijayan, and C. K. Wong. New algorithms for the rectilinear Steiner tree problem. IEEE Transactions on Computer-Aided Design, 9:185-193, 1990.
X. Hong, T. Xue, E. S. Kuh, C.-K. Cheng, and J. Huang. Performance-driven Steiner tree algorithms for global routing. In Proceedings of the Thirtieth Design Automation Conference, pages 177-181, 1993.
J. N. Hooker. Solving nonlinear multiple-facility network location problems. Networks, 19:117-133, 1989.
F. K. Hwang and D. Z. Du. Steiner minimal trees on the Chinese checkerboard. Mathematics Magazine, 64:332-339, 1991.
F. K. Hwang and Y. C. Yao. Comments on Bern's probabilistic results on rectilinear Steiner trees. Algorithmica, 5:591-598, 1990.
F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. North-Holland, Amsterdam, Netherlands, 1992.
R. Z. Hwang, R. C. Chang, and R. C. T. Lee. The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica, 9:398-423, 1993.
F. K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics, 30:104-114, 1976.
F. K. Hwang. An o(n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM, 26:177-182, 1979.
F. K. Hwang. A linear time algorithm for full Steiner trees. Operations Research Letters, 4:235-237, 1986.
T. Ichimori. A shortest path approach to a multifacility minimax location problem with rectilinear distances. Journal of the Operations Research Society of Japan, 28:269-284, 1985.
E. Ihler. Bounds on the quality of approximate solutions to the group Steiner problem. Technical Report 23, Institut für Informatik, Universität Freiburg, Freiburg, Germany, 1990. (PostScript)
E. Ihler. The complexity of approximating the class Steiner tree problem. Technical Report 32, Institut für Informatik, Universität Freiburg, Freiburg, Germany, 1991. (PostScript)
E. Ihler. The rectilinear class Steiner tree problem for intervals on two parallel lines. Technical Report 47, Institut für Informatik, Universität Freiburg, Freiburg, Germany, 1993. (PostScript)
A. O. Ivanov and A. A. Tuzhelin. Minimal networks: The Steiner problem and its generalizations. CRC Press, 1994.
B. A. Julstrom. A genetic algorithm for the rectilinear Steiner problem. In Proceedings of the Fifth International Conference on Genetic Algorithms, 1993.
A. B. Kahng and G. Robins. A new class of iterative Steiner tree heuristics with good performance. IEEE Transactions on Computer-Aided Design, 11:893-902, 1992.
A. B. Kahng and G. Robins. On performance bounds for a class of rectilinear Steiner tree heuristics in arbitrary dimension. IEEE Transactions on Computer-Aided Design, 11, 1992.
A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Norwell, Massachusetts, 1995.
K. Kalpakis and A. T. Sherman. Probabilistic analysis of an enhanced partitioning algorithm for the Steiner problem in R^d. Networks, 24:147-159, 1994. (PostScript)
Firstname Kapsalis, Firstname Rayward-Smith, and Firstname Smith. Solving the graphical Steiner tree problem using genetic algorithms. Journal of the Operational Research Society, 44, 1993.
R. M. Karp. On the computational complexity of combinatorial problems. Networks, 5:45-68, 1975.
M. Kaufmann, S. Gao, and K. Thulasiraman. On Steiner minimal trees in grid graphs and its application to VLSI layout. In Proceedings of the International Symposium on Algorithms and Computation, volume 834 of Lecture Notes in Computer Science, pages 351-359. Springer-Verlag, Berlin, Germany, 1994.
P. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted Steiner trees. Journal of Algorithms, 19:104-115, 1995.
T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality. Technical Report SC 96-42, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany, 1996. (PostScript)
C. K. Koh. Steiner problem in octilinear routing model. Master's thesis, National University of Singapore, 1995. (PostScript)
J. Komlós and M. T. Shing. Probabilistic partitioning algorithms for the rectilinear Steiner problem. Networks, 15:413-423, 1985.
B. Korte, H. J. Prömel, and A. Steger. Steiner trees in VLSI-layout. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, editors, Paths, Flows, and VLSI-Layout, pages 185-214. Springer-Verlag, Berlin, Germany, 1990.
L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, 15:141-145, 1981.
R. R. Ladeira de Matos. A rectilinear arborescence problem. PhD thesis, Department of Engineering Production, University of Birmingham, Birmingham, England, 1979.
J. H. Lee, N. K. Bose, and F. K. Hwang. Use of Steiner's problem in suboptimal routing in rectilinear metric. IEEE Transactions on Circuits and Systems, pages 470-476, 1976.
T. Lengauer. Combinatorial algorithms for integrated circuit layout. Wiley & Sons, New York, New York, 1990.
F. D. Lewis, W. C. Pong, and N. Van Cleave. Optimum Steiner tree generation. In Proceedings of the Second Great Lakes Symposium on VLSI, pages 207-212, 1992.
R. F. Love, G. O. Wesolowsky, and S. A. Kraemer. A multifacility minimax location method for Euclidean distances. International Journal of Production Research, 11:37-45, 1973.
T. Matsumoto, N. Saigan, and K. Tsuji. A new efficient approximation algorithm for the Steiner tree problem in rectilinear graph. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 2874-2876, 1990.
Z. A. Melzak. On the problem of Steiner. Canadian Mathematics Bulletin, 4:143-149, 1961.
K. Mikami and K. Tabuchi. A computer program for optimal routing of printed circuit connectors. IFIPS Proceedings, H47:1475-1478, 1968.
S. Mirayala, J. Hashmi, and N. Sherwani. Switchbox Steiner tree problem in presence of obstacles. In Proceedings of the International Conference on Computer-Aided Design, pages 536-539, 1991.
A. Ng, P. Raghavan, and C. D. Thompson. A language for describing rectilinear Steiner tree configurations. In Proceedings of the Twenty-third Design Automation Conference, pages 574-580, 1986.
Firstname Prodon. Steiner trees with n terminals among n+1 nodes. Operations Research Letters, 11:125-133, 1992.
H. J. Prömel and A. Steger. RNC-approximation algorithms for the Steiner problem. In R. Reischuk and M. Morvan, editors, Proceedings of the Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 559-570. Springer-Verlag, Berlin, Germany, 1997.
J. S. Provan. A polynomial algorithm for the Steiner tree problem on terminal-planar graphs. Technical Report 83/10, Department of Operations Research, University of North Carolina, Chapel Hill, North Carolina, 1983.
J. S. Provan. Convexity and the Steiner tree problem. Networks, 18:55-72, 1988.
S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor. The rectilinear Steiner arborescence problem. Algorithmica, 7:277-288, 1992.
S. Ravada and A. T. Sherman. Experimental evaluation of a partitioning algorithm for the Steiner tree problem in R² and R³. Networks. (to appear). (PostScript)
D. S. Richards and J. S. Salowe. A simple proof of Hwang's theorem for rectilinear Steiner minimal trees. Annals of Operations Research, 33:549-556, 1991.
D. S. Richards and J. S. Salowe. A linear-time algorithm to construct a rectilinear Steiner minimal tree for k-extremal point sets. Algorithmica, 7:247-276, 1992.
Dana Richards. Fast heuristic algorithms for rectilinear Steiner trees. Algorithmica, 4:191-207, 1989.
D. S. Richards. On the effectiveness of greedy heuristics for the rectilinear Steiner problem. manuscript, 1991.
G. Robins and J. S. Salowe. On the maximum degree of minimum spanning trees. In Proceedings of the ACM Symposium on Computational Geometry, pages 250-258, 1994. (PostScript)
J. S. Salowe and D. M. Warme. An exact rectilinear Steiner tree algorithm. In Proceedings of the International Conference on Computer Design, pages 472-475, 1993.
J. S. Salowe and D. M. Warme. 35-point rectilinear Steiner minimal trees in a day. Networks, 25:69-87, 1995.
J. S. Salowe. On exact algorithms for rectilinear Steiner minimal trees. unpublished manuscript, 1992.
M. Sarrafzadeh and C. K. Wong. New directions in the rectilinear Steiner tree problem. manuscript, 1991.
M. Sarrafzadeh and C. K. Wong. Bottleneck Steiner trees in the plane. IEEE Transactions on Computers, 41:370-374, 1992.
M. Sarrafzadeh and C. K. Wong. Hierarchical Steiner tree construction in uniform orientations. IEEE Transactions on Computer-Aided Design, 11:1095-1103, 1992.
M. Sarrafzadeh and C. K. Wong. An Introduction to VLSI Physical Design. McGraw-Hill, 1996.
M. L. Shore, L. R. Foulds, and P. B. Gibbons. An algorithm for the Steiner problem in graphs. Networks, 12:323-333, 1982.
A. F. Sidorenko. On minimal rectilinear Steiner trees. Diskretnaya Matematika, 1:28-37, 1989. (In Russian).
J. M. Smith and J. S. Liebman. Steiner trees, Steiner circuits, and the interference problem in building design. Engineering Optimization, 4:15-36, 1979.
J. M. Smith, D. T. Lee, and J. S. Liebman. An O(n log n) heuristic algorithm for the rectilinear Steiner minimal tree problem. Engineering Optimization, 4:179-192, 1980.
W. D. Smith. How to find Steiner minimal trees in Euclidean d-space. Algorithmica, 7:137-177, 1992.
T. L. Snyder. Lower bounds for rectilinear Steiner trees in bounded space. Information Processing Letters, 37:71-74, 1991.
J. Soukup. On minimum cost networks with nonlinear costs. SIAM Journal on Applied Mathematics, 29:571-581, 1975.
B. C. Tansel, R. L. Francis, and T. J. Lowe. Location on networks: A survey; part I: The p-center and p-median problems. Management Science, 29:482-497, 1983.
C. D. Thomborson, L. L. Deneen, and G. M. Shute. Computing a rectilinear Steiner minimal tree in O(n^O( sqrt n)) time. In A. Albrecht and K. Mehlhorn, editors, Parallel Algorithms and Architectures, volume 269 of Lecture Notes in Computer Science, pages 176-183. Springer-Verlag, Berlin, Germany, 1987.
C. D. Thomborson, B. Alpern, and L. Carter. Rectilinear Steiner tree minimization on a workstation. In N. Dean and G. E. Shannon, editors, Computational Support for Discrete Mathematics, volume 15 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 119-136. American Mathematical Society, Providence, Rhode Island, 1994.
J. A. White. A quadratic facility location problem. AIIE Transactions, 3:156-157, 1971.
P. Winter. An algorithm for the Steiner problem in the Euclidean plane. Networks, 15:323-345, 1985.
P. Winter. Steiner problem in networks: A survey. Networks, 17:129-167, 1987.
P. Winter. Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Applied Mathematics, 47:187-206, 1993.
P. Winter. Reductions for the rectilinear Steiner tree problem. manuscript, 1994.
Y. T. Wong and M. Pecht. Approximating the Steiner tree in the placement process. Journal of Electronic Packaging, 111:228-235, 1989.
Y. T. Wong and M. Pecht. A solution for Steiner's problem. In M. Pecht, editor, Placement and Routing of Electronic Modules, pages 261-304. Marcel Dekker, New York, New York, 1993.
Y. T. Wong. Steiner tree oriented placement. Master's thesis, Department of Mechanical Engineering, University of Maryland, College Park, Maryland, 1988.
Y. Y. Yang and O. Wing. Optimal and suboptimal solution algorithms for the wiring problem. In Proceedings of the International Symposium on Circuit Theory, pages 154-158, 1972.
A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11:721-736, 1982.
A. Z. Zelikovsky. An 11/6-approximation algorithm for the Steiner problem on graphs. In Proceedings of the Fourth Czechoslovakian Symposium on Combinatorics, Graphs, and Complexity, pages 351-354, 1992.
A. Z. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9:463-470, 1993.
A. Z. Zelikovsky. A faster approximation algorithm for the Steiner tree problem in graphs. Information Processing Letters, 46:79-83, 1993.