Open Collections

Maximum Spanning k-Tree: A Case Study

Banff International Research Station for Mathematical Innovation and Discovery

The Maximum Spanning Backbone k-Tree (BkT) problem, for k 2, is to find a maximum weight spanning k-tree from the input edge-weighted graph with a designated Hamiltonian path to be desired in the output spanning graph. Originally motivated by research in bio-molecular 3D structure prediction, BkT turns out a typical problem in a new class of languages definable beyond Monadic Second Order logic. We show that, unlike the Maximum Spanning k-Tree problem that is NP-hard for even k = 2, the BkT problem is solvable in time O(nk+1), for every fixed k 2. While there is evidence of difficulty to improve the polynomial degree k + 1 to any number lower, we show that there are O(n3)-time algorithms to approximate the BkT problem to the ratio k(k

Mathematics; Computer science; Combinatorics; Theoretical computer science

video/mp4

Author affiliation: University of Georgia

2016-06-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/58242

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/