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

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

Maximum matching based approximation algorithms for precedence constrained scheduling problems

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

Fig.1 A precedence graph $ G = (V, E) $ and its spine $ G[U] $ (left), where the unfilled vertices form into $ U $ and the four filled vertices form into $ R $; $ U^1 = \{u_3, u_5, u_6\} $ and the auxiliary bipartite graph $ H = (U^1, R, E^1) $ (right), in which the gray directed edges are precedence and the dashed undirected edges are in $ E^1 $. A matching in $ H $, $ M = \{(u_5, r_2), (u_6, r_{41})\} $ with its two edges highlighted, becomes $ \{(u_5, r_5), (u_6, r_{41})\} $ after the upgrading process, since $ r_5 $ is a successor of $ r_2 $; and further becomes $ \{(u_5, r_{41}), (u_6, r_5)\} $ after the de-crossing process, which is non-upgradeable and non-crossing