Browsing Bergen Open Research Archive by Author "Souza, Uéverton S."
Now showing items 1-3 of 3
-
Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances
Duarte, Gabriel; Oliveira, Mateus De Oliveira; Souza, Uéverton S. (Journal article; Peer reviewed, 2021)Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies ... -
Reducing Graph Transversals via Edge Contractions
Lima, Paloma T.; dos Santos, Vinicius F.; Sau, Ignasi; Souza, Uéverton S. (Journal article; Peer reviewed, 2020)For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least ... -
Taming Graphs with No Large Creatures and Skinny Ladders
Gajarský, Jakub; Jaffke, Lars; Lima, Paloma Thome de; Novotná, Jana; Pilipczuk, Marcin; Rzążewski, Paweł; Souza, Uéverton S. (Journal article; Peer reviewed, 2022)We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder ...