Parallel algorithms for single row routing in narrow streets

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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 S. Das Articles by S. Saxena

8th International Conference on VLSI Design

New Delhi, India

January 04-January 07

ISBN: 0-8186-6905-5

	ASCII Text	x
	S. Das, S. Saxena, "Parallel algorithms for single row routing in narrow streets," VLSI Design, International Conference on, pp. 13, 8th International Conference on VLSI Design, 1995.

	BibTex	x
	@article{ 10.1109/ICVD.1995.512070, author = {S. Das and S. Saxena}, title = {Parallel algorithms for single row routing in narrow streets}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {1995}, isbn = {0-8186-6905-5}, pages = {13}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512070}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Parallel algorithms for single row routing in narrow streets SN - 0-8186-6905-5 SP EP A1 - S. Das, A1 - S. Saxena, PY - 1995 KW - parallel algorithms; network routing; integrated circuit layout; circuit layout CAD; VLSI; parallel algorithms; single row routing; narrow streets; optimal layout; CREW PRAM; tree machine; VLSI layout; IC design VL - 0 JA - VLSI Design, International Conference on ER -

S. Das, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kanpur, India

S. Saxena, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kanpur, India

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512070

In this paper, the problem, of obtaining an optimal layout for the single row routing problem in narrow streets (maximum number of tracks in either street is at most 2) on parallel computers is studied. An O(log n) time parallel algorithm with O(n/logn) processors on a CREW PRAM and an O(log/sup 2/n) time cost-optimal algorithm on a tree machine is obtained.

Index Terms:

parallel algorithms; network routing; integrated circuit layout; circuit layout CAD; VLSI; parallel algorithms; single row routing; narrow streets; optimal layout; CREW PRAM; tree machine; VLSI layout; IC design

Citation:

S. Das, S. Saxena, "Parallel algorithms for single row routing in narrow streets," vlsid, pp.13, 8th International Conference on VLSI Design, 1995

Peer Review Notice | Give Us Feedback

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