Page 62 - 《软件学报》2024年第6期

2638 软件学报 2024 年第 35 卷第 6 期

SSA 形式的线性结构程序 P , 其对应的干涉图为区间图, 对于区间图我们可以有更多成熟的结论.
引理 4. 区间图的 MC 问题多项式时间可解.
证明: MC 问题可以转化为图着色问题进行求解, 只需将每个顶点转化为对应色数的完全子图, 从而转换为传
统图着色问题进行求解. 根据引理 1, 区间图必定是弦图, 转换后映射到对应图着色问题中也必定为弦图. 因此区
间图的 MC 问题可以转化为弦图的图着色问题. 根据定理 2, 该问题必定在多项式时间内可解. 因此, 区间图的
MC 问题也可以在多项式时间内求解.
我们给出无需构建干涉图的理论下界算法, 如算法 1 所示, 算法在第 2 行按照变量活跃区间的末端从大到小
排序, 按照引理 3, 该顺序必定为对应区间图的完美消除序列的逆序. 我们在第 5 行对变量的每个比特进行编号,
从而将对应加权区间图转化为区间图, 对区间图的每个顶点分别进行着色, 其中每个顶点对应变量的每个比特. 算
法第 8–21 行按照完美消除序列逆序对区间图的每个顶点进行着色. 其中第 13–15 行利用了完美消除序列的性质,
在无需构建干涉图的情况下仍然能够维护每个顶点 v 的邻居节点 N(v) 的已着色情况. 该算法的时间复杂度为
[23]
O(|V|+|E|) , 其中排序算法的时间复杂度通常为 O(|V|log|V|) , 但在该问题中, 可以利用桶排序算法加速到 O(|V|) .
算法 1. 理论下界分析.

Input: 变量列表 V , 每个变量 v ∈ V 的位宽 W v 与活跃区间 I v ;
Output: 理论下界 L .

1. function LowerBound(V,W,I)
2. Sort(V,key ← lambda v : I v .end,reversed ← True)

3. M ← 0
4. for v ∈ V do
5. index v ← [M, M +W v )∩N
6. M ← M +W v
7. end for
freeColor i ← True,∀i ∈ [0, M)∩N
8.
9. Color v ← ∅,∀v ∈ V
10. lastEnd ← I V 0 .end
11. kill i ← ∅,∀i ∈ [0,lastEnd)∩N
12. for v ∈ V do
13. kill I v .start ← kill I v .start ∪{v}
← True,∀i ∈ index u ,u ∈ kill k ,k ∈ [I v .end,lastEnd]∩N
14. freeColor color i
15. lastEnd ← I v .end
16. for i ∈ index v do
17. j ← min{k|freeColor k = True}
18. Color v ← Color v ∪{v}
19. freeColor j ← False
20. end for
21. end for
22. L ← max(Color)
23. return L,Color,index
24. end function

图 3(a) 显示了例 1 程序对应的干涉图, 图中的顶点 a,b,c,d,e 分别被等分为 5,6,4,3,7 份, 代表每个顶点可以