CAJ | 학술논문

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku+k1)|G|+1.26ku+k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku+k1)|G|+1.1892ku+k1),极大地改进了目前的最好结果.
수착VLSI(초대규모집성전로)기술적발전,관우가중구진렬이분도적수약속최소점복개(Min-CVCB)문제수도료흔다문헌적관주.작위점복개문제적자문제,해문제이피증명시NP-완전문제.인문이용핵심화화분지즉사급출료시간복잡도위O((ku+k1)|G|+1.26ku+k1)적목전최호산법,연이잉불능만족실제공정적수요.통과진일보심입분석이분도적결구,대함유권치대우혹등우3적괴적련통자도분석기가능련접정황후충분이용"련암시"기술화분지수색기술래건립기신적수색체추관계;대우분지후적괴제출료일충동태규화산법,기가재다항식시간내완성처리.정개삼수산법적운행시간위O((ku+k1)|G|+1.1892ku+k1),겁대지개진료목전적최호결과.