請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38308
標題: An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-arc Graphs with Applications
作者: M.J.Atallah
D.Z.Chen
D.T.Lee
關鍵字: Shortest paths
Interval graphs
Circular-arc graphs
Union-find algorithms
Minimum circle cover
出版社: Springer-Verlag
摘要: We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.
URI: http://hdl.handle.net/11455/38308
ISSN: 0178-4617
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。