Approximation algorithms for two-machine flow-shop scheduling with a conflict graph

Yinhui Cai, Guangting Chen, Yong Chen +4

Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the ob…