Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Correlating Theory and Practice in Finding Clubs and Plexes
Aleksander Figiel, Tomohiro Koana, André Nichterlein +1
Finding large "cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum -clubs and -plexes, i.e., graphs of diameter and graphs w…
cs.DS2022
There and Back Again: On Applying Data Reduction Rules by Undoing Others
Aleksander Figiel, Vincent Froese, André Nichterlein +1
Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm th…