Assistant Professor of Computer Science Darren Strash recently presented a paper at the virtual SIAM Symposium on Algorithm Engineering and Experiments (ALENEX22).
“Effective Data Reduction for the Vertex Clique Cover Problem,” co-authored by Louise Thompson ’21, resulted from research the two conducted during the summer of 2019, as well as Thompson’s senior thesis research.
The paper introduces the pair’s new data reduction techniques, or rules, to solve the minimum vertex clique cover (VCC) problem on graphs with up to millions of vertices. They noted that “practical rules for the VCC problem … are nearly nonexistent” and said that their new techniques “enable us to solve large, sparse, real-world graphs significantly faster than the state of the art.”
