Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/37815
標題: Optimal algorithms for interval graphs
作者: Wang, Y.L.
余明興
Chiang, K.C.
Yu, M.S.
關鍵字: parallel algorithm
spanning tree
connected component
single source
all destinations
eccentricity
interval graph
graph theory
EREW PRAM
computational model
parallel algorithm
期刊/報告no:: Journal of Information Science and Engineering, Volume 14, Issue 2, Page(s) 449-459.
摘要: In this paper, simple optimal algorithms are presented for solving some problems related to interval graphs. These problems are the connected component problem, the spanning tree problem, the eccentricity problem, and the single source all destinations shortest path problem. All of the above four problems can be solved in linear time if the endpoints of the intervals are sorted. Moreover, our algorithms can be parallelized very easily so that the above problems can be solved in O(log n) time with O(n/log n) processors using the EREW PRAM model.
URI: http://hdl.handle.net/11455/37815
ISSN: 1016-2364
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.