K線性廣播路徑問題

Full metadata record

DC Field	Value	Language
dc.contributor.author	廖勝強	en_US
dc.contributor.author	LIAO,SHENG-QIANG	en_US
dc.contributor.author	張鎮華	en_US
dc.contributor.author	ZHANG,ZHEN-HUA	en_US
dc.date.accessioned	2014-12-12T02:08:45Z	-
dc.date.available	2014-12-12T02:08:45Z	-
dc.date.issued	1990	en_US
dc.identifier.uri	http://140.113.39.130/cdrfb3/record/nctu/#NT792507007	en_US
dc.identifier.uri	http://hdl.handle.net/11536/55561	-
dc.description.abstract	1989年時, Chou和Gopalむ3め證明線性廣播路徑問題在一般圖型上是NP-complete,而且提供了一個O（n ）的演算法解決了在一般“樹”上的此種問題。而在本篇論文，首先我們提出一個O（n log n）的演算法去解決在“樹”上的Ｋ線性廣播路徑問題。所謂Ｋ線性廣播路徑問題，就是本來的廣播路徑問題再限制它最多只能有Ｋ條路徑。再來，如果我們在Ｋ線性廣播路徑問題上，考慮“樹”的每個邊最多只能通過一定數量的路徑，則我們有一個O（n ）的演算法去解決它。	zh_TW
dc.language.iso	zh_TW	en_US
dc.subject	K線性	zh_TW
dc.subject	廣播路徑	zh_TW
dc.subject	樹	zh_TW
dc.title	K線性廣播路徑問題	zh_TW
dc.type	Thesis	en_US
dc.contributor.department	應用數學系所	zh_TW
Appears in Collections:	Thesis