References

M. J. Alexander, J. P. Cohoon, J. L. Ganley, and G. Robins,
An ArchitectureIndependent Approach to FPGA Routing Based on
MultiWeighted Graphs, in Proc. European Design Automation Conf.,
Grenoble, France, September 1994, pp. 259264.

M. J. Alexander and G. Robins, A New Approach to FPGA Routing Based
on MultiWeighted Graphs, in Proc. ACM/SIGDA Intl. Workshop on
FieldProgrammable Gate Arrays, Berkeley, CA, February 1994.

S. D. Brown, R. J. Francis, J. Rose, and Z. G. Vranesic,
FieldProgrammable Gate Arrays, Kluwer Academic Publishers, Boston, MA,
1992.

Y.W. Chang, S. Thakur, K. Zhu, and D. F. Wong, A New Global Routing
Algorithm for FPGAs, in Proc. IEEE Intl. Conf. ComputerAided Design, San
Jose, CA, November 1994.

J. Cong, K. S. Leung, and D. Zhou, PerformanceDriven Interconnect
Design Based on Distributed RC Delay Model, in Proc. ACM/IEEE Design
Automation Conf., Dallas, June 1993, pp. 606611.

E. W. Dijkstra, A Note on Two Problems in Connection With Graphs,
Numerische Mathematik, 1 (1959), pp. 269271.

J. L. Ganley, private communication, April, 1994.

J. Griffith, G. Robins, J. S. Salowe, and T. Zhang,
Closing the Gap: NearOptimal Steiner Trees in Polynomial Time,
IEEE Trans. ComputerAided Design, 13 (1994), pp. 13511365.

F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree
Problem, NorthHolland, 1992.

A. B. Kahng and G. Robins, A New Class of Iterative Steiner Tree
Heuristics With Good Performance, IEEE Trans. ComputerAided Design, 11
(1992), pp. 893902.

A. B. Kahng and G. Robins, On Optimal Interconnections for VLSI,
Kluwer Academic Publishers, Boston, MA, 1995.
[here is the tableofcontents and intro of this book]

L. Kou, G. Markowsky, and L. Berman, A Fast Algorithm for Steiner
Trees, Acta Informatica, 15 (1981), pp. 141145.

G. G. Lemieux and S. D. Brown, A Detailed Routing Algorithm for
Allocating Wire Segments in FieldProgrammable Gate Arrays, in Proc.
ACM/SIGDA Physical Design Workshop, Lake Arrowhead, CA, April 1993.

S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, The
Rectilinear Steiner Arborescence Problem, Algorithmica, (1992),
pp. 277288.

Y. Sun, T. C. Wang, C. K. Wong, and C. L. Liu, Routing for Symmetric
FPGAs and FPICs, in Proc. IEEE Intl. Conf. ComputerAided Design, Santa
Clara, CA, November 1993, pp. 486490.

S. M. Trimberger, FieldProgrammable Gate Array Technology, S. M.
Trimberger, editor, Kluwer Academic Publishers, Boston, MA, 1994.

Y.L. Wu and D. Chang, On the NPCompleteness of Regular 2D FPGA
Routing Architectures and a Novel Solution, in Proc. IEEE Intl. Conf.
ComputerAided Design, San Jose, CA, November 1994, pp. 362366.

Y.L. Wu and M. MarekSadowska, An Efficient Router for 2D Field
Programmable Gate Arrays, in European Design and Test Conf., 1994,
pp. 412416.

Xilinx, The Programmable Gate Array Data Book, Xilinx, Inc., San
Jose, California, 1994.

A. Z. Zelikovsky, An 11/6 Approximation Algorithm for the Network
Steiner Problem, Algorithmica, 9 (1993), pp. 463470.