Latest Algorithms on Particular Graph Classes

Published in IOI Journal, 2020

Recommended citation: T Do, T Pham, C Than. (2020). "Latest Algorithms on Particular Graph Classes." IOI Journal.

Many optimization problems such as Maximum Independent Set, 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 to some particular graph classes such as comparability and co-comparability graph classes. In this paper, we summarize the latest algorithms solving some classical NP-hard problems on some graph classes over the years. Moreover, we apply the -redundant technique to obtain linear time O(j j) algorithms which find a Maximum Induced Matching on interval and circular-arc graphs. Inspired of these results, we have proposed some competitive programming problems for some programming contests in Vietnam in recent years [Download paper here](http://thanvietcuong.github.io/files/lastest_algo_graph_ioi.pdf) Recommended citation: T Do, T Pham, C Than. (2020). "Latest Algorithms on Particular Graph Classes." IOI Journal.