A Linear Time Algorithm for Finding ak-Tree Core |
| |
| Authors: | Akiyoshi Shioura Takeaki Uno |
| |
| Institution: | aDepartment of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku, Tokyo, 152, Japan;bDepartment of Systems Science, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku, Tokyo, 152, Japan |
| |
| Abstract: | Given a tree containingnvertices, consider the sum of the distance between all vertices and ak-leaf subtree (subtree which contains exactlykleaves). Ak-tree core is ak-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding ak-tree core for a givenk. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
