沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2009年
2期
137-140
,共4页
反问题%支撑树%哈明距离
反問題%支撐樹%哈明距離
반문제%지탱수%합명거리
讨论了瓶颈型哈明距离下费用受限制的约束最小支撑树反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型哈明距离来衡量修改的费用,且修改的总费用不超过给定的上界.利用转化的思想,给出瓶颈型哈明距离下费用受限制的约束最小支撑树反问题的多项式算法及证明.
討論瞭瓶頸型哈明距離下費用受限製的約束最小支撐樹反問題,通過脩改給定網絡邊上的權,使得脩改後網絡中指定的支撐樹是最小支撐樹併且支撐樹中的最大邊的權不超過給定的常數,用瓶頸型哈明距離來衡量脩改的費用,且脩改的總費用不超過給定的上界.利用轉化的思想,給齣瓶頸型哈明距離下費用受限製的約束最小支撐樹反問題的多項式算法及證明.
토론료병경형합명거리하비용수한제적약속최소지탱수반문제,통과수개급정망락변상적권,사득수개후망락중지정적지탱수시최소지탱수병차지탱수중적최대변적권불초과급정적상수,용병경형합명거리래형량수개적비용,차수개적총비용불초과급정적상계.이용전화적사상,급출병경형합명거리하비용수한제적약속최소지탱수반문제적다항식산법급증명.
