The Open Collections website will be undergoing maintenance on Wednesday December 7th from 9pm to 11pm PST. The site may be temporarily unavailable during this time.

BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Maximum Spanning k-Tree: A Case Study Cai, Liming


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

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International