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

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

Maximum matching based approximation algorithms for precedence constrained scheduling problems

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

Fig.5 The spine precedence graph $ G = (V, E) $ of the instance showing the tightness of the ratio: Each layer $ U_i $ is indicated by a dashed oval and the directions of all the edges are downwards