哈明距离下费用受限制约束最小支撑树反问题

摘要

讨论了瓶颈型哈明距离下费用受限制的约束最小支撑树反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型哈明距离来衡量修改的费用,且修改的总费用不超过给定的上界.利用转化的思想,给出瓶颈型哈明距离下费用受限制的约束最小支撑树反问题的多项式算法及证明.