Conditional preconditioning

Szabó, Sándor and Zaválnij, Bogdán (2021) Conditional preconditioning. In: Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21). Society for Industrial and Applied Mathematics (SIAM), Philadelphia, &. ISBN 9781611976830

Preview

Text ACDA21_paper_55.pdf Download (210kB) | Preview

Abstract

In the field of combinatorial optimization preconditioning methods prove to be of crucial importance. We present a generic way of modifying some of these methods so that they are more effective in reducing the problem size. As an example we use the k-clique decision problem and two sets of kernelization methods. One set is based on coloring the neighborhood of a node or edge, the other is based on dominance of neighborhoods. We show that we can not only delete edges but put them back and thus delete more nodes and edges from the graph in the end. The presented method is versatile and can possibly be used in other examples as well.

Actions (login required)

View Item