23 citations · 60 across the 50 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Dynamic programming on bipartite tree decompositions
Lars Jaffke, Laure Morelle, Ignasi Sau +1
We revisit a graph width parameter that we dub bipartite treewidth (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal numb…
math.CO2023
Redicolouring digraphs: directed treewidth and cycle-degeneracy
Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau
Given a digraph on vertices and a vertex , the cycle-degree of is the minimum size of a set intersecting every directed…
math.CO2023
New Menger-like dualities in digraphs and applications to half-integral linkages
Victor Campos, Jonas Costa, Raul Lopes +1
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to…