4 papers
On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy
Gabriel L. Duarte, Uéverton S. Souza
In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems that are FPT when parameterized by the treewidth of the complement graph (called co-treewidth). Since the dege…
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…
A note on independent sets in sparse-dense graphs
Uéverton S. Souza
Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani [STOC 1999, SIDMA 2003] as a tool to solve partitioning problems. In this paper, the following result conc…
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…