Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Enumeration kernels for Vertex Cover and Feedback Vertex Set
Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos +1
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creig…
cs.DS2024
Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins +1
A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matc…