1 citations · 1 across the 4 of their papers we have counts for
10 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…