EDBT 2026 Demo / reviewers in the wild / expert
Uéverton S. Souza
dblp:48/11143 · also Uéverton dos Santos Souza
· DBLP profile ↗
6ranked-venue papers in the field
0as first author
3since 2021 · last 2027
0000-0002-5320-9209ORCID · verified
Domains — venue-derived; a paper can count in several
Other / Interdisciplinary · 5Database Systems & Data Management · 1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2027 | On the maximum minimal set cover problem
Lucas Fraga Damasceno, Felipe Ribeiro Mendonça, Vinicius Prestes do Nascimento, Cristiane Magarinos Sampaio, Alan David Santos, Marcelo Miguel Alves da Silva, Uéverton S. Souza |
Inf. Process. Lett. | 7 |
| 2025 | On conflict-free cuts: Algorithms and complexityabstractOne way to define the Matching Cut problem is: Given a graph G, is there an edge-cut M of G such that M is an independent set in the line graph of G? We propose the more general Conflict-Free Cut problem: Together with the graph G, we are given a so-called conflict graph Gˆ on the edges of G, and we ask for an edge-cutset M of G that is independent in Gˆ. Since conflict-free settings are popular generalizations of classical optimization problems and Conflict-Free Cut was not considered in the literature so far, we start the study of the problem. We show that the problem is NP-complete even when the maximum degree of G is 5 and Gˆ is 1-regular. The same reduction implies an exponential lower bound on the solvability based on the Exponential Time Hypothesis. We also give parameterized complexity results: We show that the problem is fixed-parameter tractable with the vertex cover number of G as a parameter, and we show W[1]-hardness even when G has a feedback vertex set of size one, and the clique cover number of Gˆ is the parameter. Since the clique cover number of Gˆ is an upper bound on the independence number of Gˆ and thus the solution size, this implies W[1]-hardness when parameterized by the cut size. We list polynomial-time solvable cases and interesting open problems. At last, we draw a connection to a symmetric variant of SAT. Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza |
Inf. Process. Lett. | 3 |
| 2024 | Recognizing well-dominated graphs is coNP-complete
Akanksha Agrawal 0001, Henning Fernau, Philipp Kindermann, Kevin Mann, Uéverton S. Souza |
Inf. Process. Lett. | 5 |
| 2018 | On the hardness of finding the geodetic number of a subcubic graph
Letícia Rodrigues Bueno, Lucia Draque Penso, Fábio Protti, Victor R. Ramos, Dieter Rautenbach, Uéverton S. Souza |
Inf. Process. Lett. | 6 |
| 2018 | An efficient similarity-based approach for comparing XML documents
Alessandreia Marta de Oliveira, Gabriel Tessarolli, Gleiph Ghiotto, Bruno Pinto, Fernando Campello, Matheus Marques, Carlos Roberto Carvalho Oliveira, Igor Rodrigues, Marcos Kalinowski, Uéverton S. Souza, Leonardo Murta 0001, Vanessa Braganholo |
Inf. Syst. | 10 |
| 2017 | Decycling with a matching
Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme Luiz Szwarcfiter |
Inf. Process. Lett. | 3 |