首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
正在获取相似文献,请稍候...
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号