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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.ipl.2008.09.004 | Inf. Process. Lett. |
Keywords | Field | DocType |
undirected tree,linear time algorithm,tree-covering problem,third-party data distribution,integrity verification,tree-structured data,smallest total path length,simple path,tree edge,algorithms,analysis of algorithms,tree structure | Discrete mathematics,Graph algorithms,Combinatorics,Information processing,Analysis of algorithms,Tree structured data,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
109 | 1 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mikhail J. Atallah | 1 | 3828 | 340.54 |
Greg N. Frederickson | 2 | 2176 | 307.42 |
Ashish Kundu | 3 | 250 | 22.85 |