Thumbnail rectilinear Steiner trees

The State University of New York at Buffalo March 16-March 18

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/GLSV.1995.516022

Fifth Great Lakes Symposium on VLSI ( ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by J.L. Ganley Articles by J.P. Cohoon

	ASCII Text	x
	J.L. Ganley, J.P. Cohoon, "Thumbnail rectilinear Steiner trees," Great Lakes Symposium on VLSI, pp. 46, Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), 1995.

	BibTex	x
	@article{ 10.1109/GLSV.1995.516022, author = {J.L. Ganley and J.P. Cohoon}, title = {Thumbnail rectilinear Steiner trees}, journal ={Great Lakes Symposium on VLSI}, volume = {0}, year = {1995}, issn = {1066-1395}, pages = {46}, doi = {http://doi.ieeecomputersociety.org/10.1109/GLSV.1995.516022}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Great Lakes Symposium on VLSI TI - Thumbnail rectilinear Steiner trees SN - 1066-1395 SP EP A1 - J.L. Ganley, A1 - J.P. Cohoon, PY - 1995 KW - trees (mathematics); VLSI; network routing; circuit layout CAD; field programmable gate arrays; network topology; logic CAD; dynamic programming; full-set decomposition algorithm; minimum-length set; line segments; thumbnail rectilinear Steiner tree problem; VLSI placement algorithms; geometric partitioning; global routing; field-programmable gate arrays VL - 0 JA - Great Lakes Symposium on VLSI ER -

J.L. Ganley, Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA

J.P. Cohoon, Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA

This Paper Appears in : VLSI,1995. Proceedings., Fifth Great Lakes Symposium on on Pages: 46 - 49 This Conference was Held : 16-18 March1995 1995 ISBN: 0-8186-7035-5 IEEE Catalog Number: 95TH8042 Total Pages: xv+274 References Cited: 19 Accession Number: 5137489 Abstract: The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a full-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms based on geometric partitioning and in global routing of field-programmable gate arrays.

Index Terms:

trees (mathematics); VLSI; network routing; circuit layout CAD; field programmable gate arrays; network topology; logic CAD; dynamic programming; full-set decomposition algorithm; minimum-length set; line segments; thumbnail rectilinear Steiner tree problem; VLSI placement algorithms; geometric partitioning; global routing; field-programmable gate arrays

Citation:

J.L. Ganley, J.P. Cohoon, "Thumbnail rectilinear Steiner trees," glsvlsi, pp.46, Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.