Poster Presentation


More information here (page 261)

Many optimization problems such as Maximum Independent Set, Maximum Matching, Maximum Clique, Minimum Clique Cover and Maximum Induced Matching are NP-hard on general graphs. However, they could be solved in polynomial time when restricted on some special graph classes such as perfect graphs, comparability graphs and co-comparability graphs. In this presentation, we will introduce the latest algorithms solving some classical NP-hard problems on co-compatibility graphs, including those on interval, permutation and trapezoid graphs.