A characterization of linearizable instances of the quadratic minimum spanning tree problem |
| |
Authors: | Ante Ćustić Abraham P. Punnen |
| |
Affiliation: | 1.Department of Mathematics,Simon Fraser University Surrey,Surrey,Canada |
| |
Abstract: | We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph (G=(V,E)) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in (O(|E|^2)) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|