Routing using implicit connection graphs [VLSI design

V
VLSID
1996
9th International Conference on VLSI Design: VLSI in Mobile Communication
Abstract - Routing using implicit connection graphs [VLSI design

	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
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by S.Q. Zheng Articles by J.S. Lim Articles by S.S. Iyengar

9th International Conference on VLSI Design: VLSI in Mobile Communication

Bangalore, INDIA

January 03-January 06

ISBN: 0-8186-7228-5

	ASCII Text	x
	S.Q. Zheng, J.S. Lim, S.S. Iyengar, "Routing using implicit connection graphs [VLSI design," VLSI Design, International Conference on, pp. 49, 9th International Conference on VLSI Design: VLSI in Mobile Communication, 1996.

	BibTex	x
	@article{ 10.1109/ICVD.1996.489453, author = {S.Q. Zheng and J.S. Lim and S.S. Iyengar}, title = {Routing using implicit connection graphs [VLSI design}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {1996}, issn = {1063-9667}, pages = {49}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1996.489453}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Routing using implicit connection graphs [VLSI design SN - 1063-9667 SP EP A1 - S.Q. Zheng, A1 - J.S. Lim, A1 - S.S. Iyengar, PY - 1996 KW - VLSI; integrated circuit layout; graph theory; circuit layout CAD; search problems; implicit connection graphs; shortest path related problems; minimum spanning tree problem; obstacles; sparse strong connection graph; search behavior; large VLSI design applications; VLSI layout VL - 0 JA - VLSI Design, International Conference on ER -

S.Q. Zheng, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA

J.S. Lim, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA

S.S. Iyengar, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA

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

We introduce a framework for a class of algorithms solving shortest path related problems, such as the one-to-one shortest path problem, the one-to-many shortest paths problem and the minimum spanning tree problem, in the presence of obstacles. For these algorithms, the search space is restricted to a sparse strong connection graph which is implicitly represented and its searched portion is constructed incrementally on-the-fly during search. The time and space requirements of these algorithms essentially depend on actual search behavior. These algorithms are suitable for large VLSI design applications with many obstacles.

Index Terms:

VLSI; integrated circuit layout; graph theory; circuit layout CAD; search problems; implicit connection graphs; shortest path related problems; minimum spanning tree problem; obstacles; sparse strong connection graph; search behavior; large VLSI design applications; VLSI layout

Citation:

S.Q. Zheng, J.S. Lim, S.S. Iyengar, "Routing using implicit connection graphs [VLSI design," vlsid, pp.49, 9th International Conference on VLSI Design: VLSI in Mobile Communication, 1996

Peer Review Notice | Give Us Feedback

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