3 papers
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.DM2024
Complexity of Deciding the Equality of Matching Numbers
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and…
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…