6 citations · 13 across the 8 of their papers we have counts for
11 papers
On the Complexity of the Median and Closest Permutation Problems
Luís Cunha, Ignasi Sau, Uéverton Souza
Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomic…
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
Karthik C. S., Dániel Marx, Marcin Pilipczuk +1
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no time algorithm that can solve 2-CSPs with constra…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
Exact and Parameterized Algorithms for the Independent Cutset Problem
Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza
The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is -complete even when th…
Recognizing well-dominated graphs is coNP-complete
Akanksha Agrawal, Henning Fernau, Philipp Kindermann +2
A graph is well-covered if every minimal vertex cover of is minimum, and a graph is well-dominated if every minimal dominating set of is minimum. Studies on well-co…
Linear-time Algorithms for Eliminating Claws in Graphs
Flavia Bonomo-Braberman, Julliano R. Nascimento, Fabiano S. Oliveira +2
Since many NP-complete graph problems have been shown polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given grap…
Hitting forbidden induced subgraphs on bounded treewidth graphs
Ignasi Sau, Uéverton S. Souza
For a fixed graph , the -IS-Deletion problem asks, given a graph , for the minimum size of a set such that does not contain as an ind…
The Complexity of Helly- EPG Graph Recognition
Claudson F. Bornstein, Martin Charles Golumbic, Tanilson D. Santos +2
Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph is a graph that admits a representati…
FPT algorithms to recognize well covered graphs
Rafael Araujo, Eurinardo Costa, Sulamita Klein +2
Given a graph , let and be the sizes of a minimum and a maximum minimal vertex covers of , respectively. We say that is well covered if …
On the (parameterized) complexity of recognizing well-covered (r,l)-graphs
Sancrey R. Alves, Konrad K. Dabrowski, Luerbio Faria +3
An -partition of a graph is a partition of its vertex set into independent sets and cliques. A graph is if it admits an -partition.…
Revisiting the Complexity of And/Or Graph Solution
Maise Dantas da Silva, Fábio Protti, Uéverton dos Santos Souza
This paper presents a study on two data structures that have been used to model several problems in computer science: and/or graphs and x-y graphs. An and/or graph is an acyclic di…