U. Souza

activity

20152020

collaborators

5 papers

cs.DM2020

On the Parameterized Complexity Of Grid Contraction

Saket Saurabh, Uéverton dos Santos Souza, Prafullkumar Tale

For a family of graphs $G$ , the $G$ -\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$ , and the goal is to decide if there exists $F…

cs.DS2020

Computing the Largest Bond and the Maximum Connected Cut of a Graph

Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6

The cut-set $\partial (S)$ of a graph $G = (V, E)$ is the set of edges that have one endpoint in $S \subset V$ and the other endpoint in $V ∖ S$ , and whenever $G [S]$ is connected…

cs.DS2019

Width Parameterizations for Knot-free Vertex Deletion on Digraphs

Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2

A knot in a directed graph $G$ is a strongly connected subgraph $Q$ of $G$ with at least two vertices, such that no vertex in $V (Q)$ is an in-neighbor of a vertex in $V(G)\setminus…

cs.DS2019

Computing the largest bond of a graph

Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa +2

A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$ , i.e., bonds are cut-sets that determine cuts $[S, V ∖ S]$ of $G$ such that $G [S]$ and $G[V\setmin…

math.CO2015

Graphs in which some and every maximum matching is uniquely restricted

Lucia Draque Penso, Dieter Rautenbach, Ueverton dos Santos Souza

A matching $M$ in a graph $G$ is uniquely restricted if there is no matching $M^{'}$ in $G$ that is distinct from $M$ but covers the same vertices as $M$ . Solving a problem posed by G…