Browsing Department of Informatics by Author "Sau, Ignasi"
Now showing items 1-3 of 3
-
Compound Logics for Modification Problems
Fomin, Fedor; Golovach, Petr; Sau, Ignasi; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with ... -
Dynamic Programming on Bipartite Tree Decompositions
Jaffke, Lars; Morelle, Laure; Sau, Ignasi; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of ... -
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 ...