85 citations · 144 across the 27 of their papers we have counts for
28 papers
Sub-polynomial parameterized complexity of -core
Yan S. Couto, Cristina G. Fernandes
The -core of a graph is its (unique) largest subgraph with minimum degree at least . For any , deciding whether a given vertex belongs to the -core is a P-comple…
Hardness of Dynamic Core and Truss Decompositions
Yan S. Couto, Cristina G. Fernandes
The k-core of a graph is its maximal subgraph with minimum degree at least k, and the core value of a vertex u is the largest k for which u is contained in the k-core of the graph.…
Approximations for the Steiner Multicycle Problem
Cristina G. Fernandes, Carla N. Lintzmayer, Phablo F. S. Moura
The Steiner Multicycle problem consists of, given a complete graph, a weight function on its vertices, and a collection of pairwise disjoint non-unitary sets called terminal sets,…
Independent dominating sets in planar triangulations
Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez
In 1996, Matheson and Tarjan proved that every near planar triangulation on vertices contains a dominating set of size at most , and conjectured that this upper bound can…
How heavy independent sets help to find arborescences with many leaves in DAGs
Cristina G. Fernandes, Carla N. Lintzmayer
Trees with many leaves have applications on broadcasting, which is a method in networks for transferring a message to all recipients simultaneously. Internal nodes of a broadcastin…
On the period collapse of a family of Ehrhart quasi-polynomials
Cristina G. Fernandes, José C. de Pina, Jorge L. Ramírez Alfonsín +1
A graph whose nodes have degree 1 or 3 is called a -graph. Liu and Osserman associated a polytope to each -graph and studied the Ehrhart quasi-polynomials of thes…