Clique Cover of Graphs with Bounded Degeneracy
Structural parameters of graph (such as degeneracy and arboricity) had rarely been considered when designing algorithms for (edge) clique cover problems. Taking degeneracy of graph into account, we present a greedy framework and two fixed-parameter tractable algorithms for clique cover problems. We introduce a set theoretic concept and demonstrate its use in the computations of different objectives of clique cover. Furthermore, we show efficacy of our algorithms in practice.
READ FULL TEXT