Hierarchical Exponential Search Via K-Spines

Abstract

We introduce the concept of a k-spine of a tree. A k-spine is essentially a path in the tree whose removal leaves only "less-bushy" components of a smaller pathwidth. Using a k-spine as a central guide, we introduce an O(klog dist) exponential search algorithm on a tree by searching mainly along the spine to narrow down the target's vicinity and then recursively handling the smaller components.

This was an unintentional early upload of a work-in-progress draft from an ongoing collaboration. The posting was premature and not meant for public release