优先序约束的排序问题：基于最大匹配的近似算法

张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉

Maximum matching based approximation algorithms for precedence constrained scheduling problems

An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN

Fig.3 A spine precedence graph $ G = (V, E) $ (left), in which no $ U_i $ fully precedes $ U_{i+1} $ for any $ i $; the auxiliary graph $ \overline{G} = (V, \overline{E}) $ (right), in which the edges are dashed. A lexicographically largest matching in $ \overline{G} $ is highlighted with its binary vector $ (1, 1, 0, 1, 1, 1) $, which contains no edge from $ \overline{E}(U_3, U_4) $