Efficient Algorithms for Finding a Core of a Tree with a Specified Length |
| |
| Authors: | Shietung Peng Win-tsung Lo |
| |
| Affiliation: | aDepartment of Computer Software, The University of Aizu, Aizu-Wakamatsu, Japan;bDepartment of Information Engineering, Feng Chia University, Taichung, Taiwan |
| |
| Abstract: | Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log2n) time usingO(n) processors on an EREW PRAM model. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
