K線性廣播路徑問題

Abstract

1989年時, Chou和Gopalむ3め證明線性廣播路徑問題在一般圖型上是NP-complete,而 且提供了一個O（n ）的演算法解決了在一般“樹”上的此種問題。而在本篇論文， 首先我們提出一個O（n log n）的演算法去解決在“樹”上的Ｋ線性廣播路徑問題。 所謂Ｋ線性廣播路徑問題，就是本來的廣播路徑問題再限制它最多只能有Ｋ條路徑。 再來，如果我們在Ｋ線性廣播路徑問題上，考慮“樹”的每個邊最多只能通過一定數 量的路徑，則我們有一個O（n ）的演算法去解決它。