Constructing a minimum height elimination tree of a tree in linear time |
| |
Authors: | Chung-Hsien Hsu Chong-Hui Shi |
| |
Affiliation: | a Department of Management Information System, Takming College, Taipei 11451, Taiwan, ROC b Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien 97401, Taiwan, ROC |
| |
Abstract: | Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree. |
| |
Keywords: | Trees Vertex ranking Elimination trees Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|