3 papers
cs.DS2026
A more versatile model for enumerative kernelization: a case study for Vertex Cover
Marin Bougeret, Guilherme C. M. Gomes, Ignasi Sau
Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kerne…
cs.DS2025
Enumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with t…
cs.DS2025
Revisiting Directed Disjoint Paths on tournaments (and relatives)
Guilherme C. M. Gomes, Raul Lopes, Ignasi Sau
In the Directed Disjoint Paths problem (-DDP), we are given a digraph pairs of terminals, and the goal is to find pairwise vertex-disjoint paths connecting each pair of…