A tree-covering problem arising in integrity of tree-structured data |
| |
| Authors: | Mikhail J. Atallah Greg N. Frederickson |
| |
| Affiliation: | Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA |
| |
| Abstract: | We introduce and solve a problem motivated by integrity verification in third-party data distribution: Given an undirected tree, find a minimum-cardinality set of simple paths that cover all the tree edges and, secondarily, have smallest total path lengths. We give a linear time algorithm for this problem. |
| |
| Keywords: | Algorithms Analysis of algorithms Graph algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
