| dc.creator (作者) | 許芳榮;沈錳坤;趙考蜀;李家同 | zh_TW |
| dc.date (日期) | 2005-05 | en_US |
| dc.date.accessioned | 16-Dec-2008 16:41:12 (UTC+8) | - |
| dc.date.available | 16-Dec-2008 16:41:12 (UTC+8) | - |
| dc.date.issued (上傳時間) | 16-Dec-2008 16:41:12 (UTC+8) | - |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/14987 | - |
| dc.description.abstract (摘要) | In this paper, we consider some shortest path related problems on interval and circular-arc graphs. For the all-pair shortest path query problem on interval and circular-arc graphs, instead of using the sophisticated technique, we propose simple parallel algorithms using only the parallel prefix and suffix computations and the Euler tour technique. Our preprocessing algorithms run in O(log n) time using O(nlog n) processors. Using the data structure constructed by our preprocessing algorithms, a query of the length of a shortest path between any two vertices can be answered in constant time by using a single processor. For the hinge vertex problem on interval graphs, we propose an O(log n) time algorithm using O(nlog n) processors. It leads to a linear time sequential algorithm. Our algorithms work on the EREW PRAM model. | en-US |
| dc.format | application/ | en_US |
| dc.language | en | en_US |
| dc.language | en-US | en_US |
| dc.language.iso | en_US | - |
| dc.relation (關聯) | Journal of Information Science and Engineering, 21(3), 627-642 | en_US |
| dc.subject (關鍵詞) | parallel algorithms,EREW PRAM,all-pair shortest path,hinge vertex,interval graph | en-US |
| dc.title (題名) | Some Optimal Parallel Algorithms on Interval and Circular-Arc Graphs | en_US |
| dc.type (資料類型) | article | en |
