QQ客服 官方微博 反馈留言

	Steiner Minimal Trees in rectilinear and octilinear planes
	Shang, Song Pu ; Jing, Tong
	2010-05-06 ; 2010-05-06
关键词	Steiner minimal tree minimum spanning tree rectilinear plane octilinear plane ORIENTATIONS Mathematics, Applied Mathematics
中文摘要	This paper considers the Steiner Minimal Tree (SMT) problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI: The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.
语种	英语 ; 英语
出版者	SPRINGER HEIDELBERG ; HEIDELBERG ; TIERGARTENSTRASSE 17, D-69121 HEIDELBERG, GERMANY
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/10268]
专题	清华大学
推荐引用方式 GB/T 7714	Shang, Song Pu,Jing, Tong. Steiner Minimal Trees in rectilinear and octilinear planes[J],2010, 2010.
APA	Shang, Song Pu,&Jing, Tong.(2010).Steiner Minimal Trees in rectilinear and octilinear planes..
MLA	Shang, Song Pu,et al."Steiner Minimal Trees in rectilinear and octilinear planes".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。