Cláudia Linhares Sales
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Cláudia Linhares Sales has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Ana Silva
Universidade Federal do Ceará
9 shared publications Frédéric Maffray
8 shared publications- Rudini Sampaio
Universidade Federal do Ceará
6 shared publications - Leonardo Sampaio
Postgraduate Program in Computer Science -PPGCC Center for Science and Technology -CCT Graphs and Computational Intelligence Lab -LAGIC State University of Ceará -UECE Fortaleza Ceará Brazil
5 shared publications Bruce Reed
4 shared publicationsFrédéric Havet
4 shared publications
Latest Publications
- Open Access
- 6 August 2023
- Published by Sociedade Brasileira de Computação
- p. 6-9
Decomposição de Fluxos em Digrafos Arco-Coloridos
Let N be a network over a digraph D and x be a feasible (s, t)-flow in N. We say that x is ℓ-splittable if it can be decomposed into up to ℓ path-flows. In this paper, we consider the problem of obtaining a path decomposition in arccoloured digraphs, such that the sum of the number of path colours is minimum. We show that, for a given flow x in a network N over an arc-coloured digraph and an integer k, it is NP-complete to decide whether there is a decomposition of x into paths, such that the sum of the number of colours of the paths is at most k, and we show some cases for which this can be done in polynomial time. Sejam N uma rede sobre um digrafo D e x um (s, t)-fluxo viável em N. Dizemos que x é ℓ-divisível se ele pode ser decomposto em até ℓ fluxos caminhos. Neste artigo, consideramos o problema de obter uma decomposição em caminhos em digrafos arco-coloridos, de modo que a soma do número de cores dos caminhos seja mínima. Nós mostramos que, dado fluxo x em uma rede N sobre um digrafo arco-colorido e um inteiro k, é NP-completo decidir se há uma decomposição de x em caminhos, tal que a soma do número de cores dos caminhos seja no máximo k, e mostramos alguns casos para os quais isso pode ser feito em tempo polinomial.
- 6 August 2023
- Published by Sociedade Brasileira de Computação
- p. 6-9
Open AccessDecomposição de Fluxos em Digrafos Arco-Coloridos
Let N be a network over a digraph D and x be a feasible (s, t)-flow in N. We say that x is ℓ-splittable if it can be decomposed into up to ℓ path-flows. In this paper, we consider the problem of obtaining a path decomposition in arccoloured digraphs, such that the sum of the number of path colours is minimum. We show that, for a given flow x in a network N over an arc-coloured digraph and an integer k, it is NP-complete to decide whether there is a decomposition of x into paths, such that the sum of the number of colours of the paths is at most k, and we show some cases for which this can be done in polynomial time. Sejam N uma rede sobre um digrafo D e x um (s, t)-fluxo viável em N. Dizemos que x é ℓ-divisível se ele pode ser decomposto em até ℓ fluxos caminhos. Neste artigo, consideramos o problema de obter uma decomposição em caminhos em digrafos arco-coloridos, de modo que a soma do número de cores dos caminhos seja mínima. Nós mostramos que, dado fluxo x em uma rede N sobre um digrafo arco-colorido e um inteiro k, é NP-completo decidir se há uma decomposição de x em caminhos, tal que a soma do número de cores dos caminhos seja no máximo k, e mostramos alguns casos para os quais isso pode ser feito em tempo polinomial.
- 1 January 2020
- Published by Springer Nature in Matemática Contemporânea
- Vol. 46 (24)
Um estudo de redes com fuxos ramificados arco-disjuntos
- 1 January 2020
- Published by Springer Nature in Matemática Contemporânea
- Vol. 46 (24)
Um estudo de redes com fuxos ramificados arco-disjuntos
- 1 May 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 261, 219-228
Minimal obstructions to 2-polar cographs
- 1 May 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 261, 219-228
Minimal obstructions to 2-polar cographs
- Open Access
Weighted proper orientations of trees and graphs of bounded treewidth
Given a simple graph $G$, a weight function $w:E(G)\rightarrow \mathbb{N} \setminus \{0\}$, and an orientation $D$ of $G$, we define $\mu^-(D) = \max_{v \in V(G)} w_D^-(v)$, where $w^-_D(v) = \sum_{u\in N_D^{-}(v)}w(uv)$. We say that $D$ is a weighted proper orientation of $G$ if $w^-_D(u) \neq w^-_D(v)$ whenever $u$ and $v$ are adjacent. We introduce the parameter weighted proper orientation number of $G$, denoted by $\overrightarrow{\chi}(G,w)$, which is the minimum, over all weighted proper orientations $D$ of $G$, of $\mu^-(D)$. When all the weights are equal to 1, this parameter is equal to the proper orientation number of $G$, which has been object of recent studies and whose determination is NP-hard in general, but polynomial-time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., $\overrightarrow{\chi}(G,w) \leq k$?) is (weakly) NP-complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on $k$. Furthermore, we present a dynamic programming algorithm to determine whether a general graph $G$ on $n$ vertices and treewidth at most ${\sf tw}$ satisfies $\overrightarrow{\chi}(G,w) \leq k$, running in time $O(2^{{\sf tw}^2}\cdot k^{3{\sf tw}}\cdot {\sf tw} \cdot n)$, and we complement this result by showing that the problem is W[1]-hard on general graphs parameterized by the treewidth of $G$, even if the weights are polynomial in $n$.Open AccessWeighted proper orientations of trees and graphs of bounded treewidth
Given a simple graph $G$, a weight function $w:E(G)\rightarrow \mathbb{N} \setminus \{0\}$, and an orientation $D$ of $G$, we define $\mu^-(D) = \max_{v \in V(G)} w_D^-(v)$, where $w^-_D(v) = \sum_{u\in N_D^{-}(v)}w(uv)$. We say that $D$ is a weighted proper orientation of $G$ if $w^-_D(u) \neq w^-_D(v)$ whenever $u$ and $v$ are adjacent. We introduce the parameter weighted proper orientation number of $G$, denoted by $\overrightarrow{\chi}(G,w)$, which is the minimum, over all weighted proper orientations $D$ of $G$, of $\mu^-(D)$. When all the weights are equal to 1, this parameter is equal to the proper orientation number of $G$, which has been object of recent studies and whose determination is NP-hard in general, but polynomial-time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., $\overrightarrow{\chi}(G,w) \leq k$?) is (weakly) NP-complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on $k$. Furthermore, we present a dynamic programming algorithm to determine whether a general graph $G$ on $n$ vertices and treewidth at most ${\sf tw}$ satisfies $\overrightarrow{\chi}(G,w) \leq k$, running in time $O(2^{{\sf tw}^2}\cdot k^{3{\sf tw}}\cdot {\sf tw} \cdot n)$, and we complement this result by showing that the problem is W[1]-hard on general graphs parameterized by the treewidth of $G$, even if the weights are polynomial in $n$. - 1 November 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 62, 261-266
The lexicographic product of some chordal graphs and of cographs preserves b-continuity
- 1 November 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 62, 261-266
The lexicographic product of some chordal graphs and of cographs preserves b-continuity
- 12 August 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1165-1180
On the b-Continuity of the Lexicographic Product of Graphs
- 12 August 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1165-1180
On the b-Continuity of the Lexicographic Product of Graphs
- 2 August 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1189-1194
Proper Orientations of Planar Bipartite Graphs
- 2 August 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1189-1194
Proper Orientations of Planar Bipartite Graphs
- 12 July 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1139-1146
The b-Continuity of Graphs with Large Girth
- 12 July 2017
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 33 (5) , 1139-1146
The b-Continuity of Graphs with Large Girth
- Open Access
Minimal obstructions to $2$-polar cographs
A graph is a cograph if it is $P_4$-free. A $k$-polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by $A$ is a complete multipartite graph with at most $k$ parts, and the subgraph induced by $B$ is a disjoint union of at most $k$ cliques with no other edges. It is known that $k$-polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed $k$. A concrete family of such forbidden induced subgraphs is known for $k=1$, since $1$-polar graphs are precisely split graphs. For larger $k$ such families are not known, and Ekim, Mahadev, and de Werra explicitely asked for the family for $k=2$. In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves $2$-polarity and also preserves the condition of being a cograph. We do not know such an operation for $k > 2$, nevertheless we believe that the results and methods discussed here will also be useful for higher $k$.Open AccessMinimal obstructions to $2$-polar cographs
A graph is a cograph if it is $P_4$-free. A $k$-polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by $A$ is a complete multipartite graph with at most $k$ parts, and the subgraph induced by $B$ is a disjoint union of at most $k$ cliques with no other edges. It is known that $k$-polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed $k$. A concrete family of such forbidden induced subgraphs is known for $k=1$, since $1$-polar graphs are precisely split graphs. For larger $k$ such families are not known, and Ekim, Mahadev, and de Werra explicitely asked for the family for $k=2$. In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves $2$-polarity and also preserves the condition of being a cograph. We do not know such an operation for $k > 2$, nevertheless we believe that the results and methods discussed here will also be useful for higher $k$. - 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 101-104
Graphs with large girth are b-continuous
- 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 101-104
Graphs with large girth are b-continuous