most significant
·
Lattes cv
·
Mathematical Reviews
·
Google Scholar
·
dblp
·
orcid
Papers in refereed journals
-
On the pebbling numbers of Flower, Blanusa and Watkins snarks
Discrete Applied Mathematics
361 (2025) 336-346
(with Matheus Adauto, Glenn Hurlbert, Diana Sasaki).
[pdf]
-
Canonical cuts of path powers
Contributions to Discrete Mathematics
19 (2024) 121-136
(with
Liliana Alcon, Luerbio Faria, Marisa Gutierrez, Sulamita Klein, Mathieu Dutour Sikiric, Uéverton Souza, Rubens Sucupira).
[pdf]
-
Parameterized algorithms for Steiner Tree and (Connected) Dominating Set on Path Graphs
Networks
84 (2024) 132-147
(with Raul Lopes, Alexsander Melo, Ana Silva).
[pdf]
-
The hardness of recognising poorly matchable graphs and the hunting of the d-snark
RAIRO Operations Research
58 (2024) 2055-2073
(with L. M. Zatesko, R. Carmo, A. L. P. Guedes, R. C. S. Machado).
[pdf]
-
On the total chromatic number of the direct product of cycles and complete graphs
RAIRO Operations Research
58 (2024) 1609-1632
(with Diane Castonguay, Luis Kowada, Caroline Patrão, Diana Sasaki, Mario Valencia-Pabon).
[pdf]
-
IFORS' Operational Research Hall of Fame: Clóvis Caesar Gonzaga
International Transactions in Operational Research
31 (2024) 2796-2798
(with Elizabeth W. Karas, Claudia Sagastizábal).
[pdf]
-
Maximum cut on interval graphs of interval count four is NP-complete
Discrete & Computational Geometry
71 (2024) 893-917
(with Alexsander Melo, Fabiano Oliveira, Ana Silva).
[pdf]
-
On the degree of trees with game chromatic number 4
RAIRO Operations Research
57 (2023) 2757-2767
(with Ana Furtado, Miguel Paiva, Simone Dantas).
[pdf]
-
On the computational difficulty of the terminal connection problem
RAIRO Theoretical Informatics and Applications
57 (2023)
(with Alexsander A. de Melo, Uéverton Souza).
[pdf]
-
On total coloring the direct product of cycles and bipartite direct product of graphs
Discrete Mathematics
346 (2023) 113340
(with Diane Castonguay, Luis Antonio Kowada, Caroline Patrão, Diana Sasaki).
[pdf]
-
MaxCut on permutation graphs is NP-complete
Journal of Graph Theory
104 (2023) 5-16
(with Alexsander A. de Melo, Fabiano S. Oliveira, Ana Silva).
[pdf]
-
Total tessellation cover: bounds, hardness, and applications
Discrete Applied Mathematics
323 (2022) 149-161
(with Alexandre Santiago de Abreu, Luis Felipe Cunha, Luis A. B. Kowada, Franklin de Lima Marquezino, Daniel Posner, Renato Portugal).
[pdf]
-
Compositions, decompositions, and conformability for total coloring on power of cycle graphs
Discrete Applied Mathematics
323 (2022) 349-363
(with Alesom Zorzi, Raphael Machado, Leandro Zatesko, Uéverton Souza).
[pdf]
-
Revising Johnson's table for the 21st century
Discrete Applied Mathematics
323 (2022) 184-200
(with Alexsander Melo, Diana Sasaki, Ana Silva).
[pdf
·
current table]
-
On total and edge coloring some Kneser graphs
Journal of Combinatorial Optimization
44 (2022) 119-135
(with Caroline Patrão, Diana Sasaki, Mario Valencia-Pabon).
[pdf]
-
Computing the zig-zag number of directed graphs
Discrete Applied Mathematics
312 (2022) 86-105
(with Mitre Dourado, Alexsander Melo, Mateus de Oliveira Oliveira, Uéverton Souza).
[pdf]
-
A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates
Journal of Universal Computer Science
27 (2021) 544-563
(with Edinelço Dalcumune, Luis Antonio Kowada, André da Cunha Ribeiro, Franklin de Lima Marquezino).
[pdf]
-
On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems
Networks
77 (2021) 559-571
(with Alexsander Melo, Uéverton Souza).
[pdf]
-
A computational complexity comparative study of graph tessellation problems
Theoretical Computer Science
858 (2021) 81-89
(with Alexandre Santiago de Abreu, Luis Felipe Cunha, Luis A. B. Kowada, Franklin de Lima Marquezino, Renato Portugal, Daniel Posner).
[pdf]
-
The guide to NP-completeness is 40 years old: An homage to David S. Johnson
Pesquisa Operacional
40 (2020) e236329
(with Luciana Buriol, Mauricio Resende, Eduardo Uchoa).
[pdf]
-
Complexity-separating graph classes for vertex, edge and total colouring
Discrete Applied Mathematics
281 (2020) 162-171.
[pdf]
-
A multivariate analysis of the strict terminal connection problem
Journal of Computer and System Sciences
111 (2020) 22-41
(with Alexsander Melo, Uéverton Souza).
[pdf]
-
On the computational complexity of closest genome problems
Discrete Applied Mathematics
274 (2020) 26-34
(with Luis Felipe Cunha, Pedro Feijão, Vinicius Santos, Luis A. B. Kowada).
[pdf]
-
The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
Theoretical Computer Science
801 (2020) 175-191
(with Alexandre Santiago de Abreu, Luis Felipe Cunha, Luis A. B. Kowada, Franklin de Lima Marquezino, Daniel Posner, Renato Portugal).
[pdf]
-
Timber game as a counting problem
Discrete Applied Mathematics
261 (2019) 193-202
(with Ana Furtado, Simone Dantas, Sylvain Gravier).
-
On the embedding of cone graphs in the line with distinct distances between neighbors
Discrete Applied Mathematics
251 (2019) 157-162
(with Rodrigo M. Zhou, Raphael Machado, Vinícius Gusmão P. de Sá).
-
On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers
Discrete Mathematics
342 (2019) 1318-1324
(with Clément Charpentier, Simone Dantas, Ana Furtado, Sylvain Gravier).
-
Sandwich and probe problems for excluding paths
Discrete Applied Mathematics
251 (2018) 146-154
(with Sophie Spirkl).
-
The sandwich problem for decompositions and almost monotone properties
Algorithmica
80 (2018) 3618-3645
(with Maria Chudnovsky, Sophie Spirkl).
-
Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
Discrete Applied Mathematics
245 (2018) 101-108
(with
Helio Macedo Filho, Zhentao Li, Raphael Machado).
-
The (k,l) partitioned probe problem: NP-complete versus polynomial dichotomy
Discrete Applied Mathematics
234 (2018) 67-75
(with Simone Dantas, Luerbio Faria, Rafael B. Teixeira).
-
Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
International Journal of Computational Geometry and Applications
27 (2017) 255-276
(with Vinícius Gusmão P. de Sá,
Guilherme Fonseca).
-
Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
Algorithmica
77 (2017) 786-814
(with Hélio Macêdo Filho, Raphael Machado).
-
The same upper bound for both:
the 2-page and the rectilinear crossing numbers of the n-cube
Journal of Graph Theory
83 (2016) 19-33
(with Luerbio Faria, Bruce Richter, Imrich Vrto).
-
On the equitable total chromatic number of cubic graphs
Discrete Applied Mathematics
209 (2016) 84-91
(with Simone Dantas, Giuseppe Mazzuoccolo, Myriam Preissmann,
Vinicius Santos, Diana Sasaki).
-
A note on the middle levels problem
Discrete Applied Mathematics
210 (2016) 290-296
(with Andreia Gusmão, Letícia Rodrigues Bueno, Rodrigo Hausen, Luerbio Faria).
-
The cost of perfection for matchings in graphs
Discrete Applied Mathematics
210 (2016) 112-122
(with Emilio Vital Brazil, Guilherme Fonseca, Diana Sasaki).
- Linear-time graph distance and diameter approximation
International Transactions in Operational Research
23 (2016) 843-851
(with Raphael Machado).
-
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
Theoretical Computer Science
618 (2016) 122-134
(with Hélio Macêdo Filho, Raphael Machado).
-
On the total coloring of generalized Petersen graphs
Discrete Mathematics
339 (2016) 1471-1475
(with Simone Dantas, Giuseppe Mazzuoccolo, Myriam Preissmann,
Vinicius Santos, Diana Sasaki).
- The (k,l)-unpartitioned probe problem NP-complete versus Polynomial dichotomy
Information Processing Letters
116 (2016) 294-298
(with Simone Dantas, Luerbio Faria, Rafael B. Teixeira).
-
A faster 1.375-approximation algorithm for sorting by transpositions
Journal of Computational Biology
22 (2015) 1044-1056
(with Luis Felipe Cunha, Luis A. B. Kowada, Rodrigo Hausen).
-
On the recognition of unit disk graphs and the distance geometry problem with ranges
Discrete Applied Mathematics
197 (2015) 3-19
(with Vinícius Gusmão P. de Sá,
Guilherme Fonseca,
Raphael Machado).
-
Biclique-colouring verification complexity and biclique-colouring power graphs
Discrete Applied Mathematics
192 (2015) 65-76
(with Helio Macedo Filho, Simone Dantas, Raphael Machado).
-
Hamiltonian cycles in unitary prefix transposition rearrangement graphs
Discrete Applied Mathematics
192 (2015) 82-86
(with Caroline Reis, Luis A. B. Kowada, Leticia Rodrigues Bueno,
Andre Cunha Ribeiro).
-
On probe co-bipartite and probe diamond-free graphs
Discrete Mathematics and Theoretical Computer Science
17 (2015) 187-200
(with Flavia Bonomo, Guillermo Durán, Luciano Grippo,
Martín Safe, Jayme Szwarcfiter).
-
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
Discrete Applied Mathematics
182 (2015) 15-24
(with Simone Dantas, Frédéric Maffray, Rafael B. Teixeira).
-
Blind-friendly von Neumann's heads or tails
The American Mathematical Monthly
121 (2014) 600-609
(with
Vinícius Gusmão P. de Sá).
-
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
Theoretical Computer Science
540 (2014) 70-81
(with Vinícius Gusmão P. de Sá,
Guilherme Fonseca,
Raphael Machado).
-
Complexity of colouring problems restricted to unichord-free and
{square,unichord}-free graphs
Discrete Applied Mathematics
164 (2014) 191-199
(with
Raphael Machado,
Nicolas Trotignon).
-
The hunting of a snark with total chromatic number 5
Discrete Applied Mathematics
164 (2014) 470-481
(with Diana Sasaki, Simone Dantas, Myriam Preissmann).
-
Advancing the transposition distance and diameter through lonely permutations
SIAM Journal on Discrete Mathematics
27 (2013) 1682-1709
(with Luis Felipe Cunha, Luis A. B. Kowada, Rodrigo Hausen).
-
Split clique graph complexity
Theoretical Computer Science
506 (2013) 29-42
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
Edge-colouring and total-colouring chordless graphs
Discrete Mathematics
313 (2013) 1547-1552
(with
Raphael Machado,
Nicolas Trotignon).
-
The P vs. NP-complete dichotomy of some challenging problems in graph
theory
Discrete Applied Mathematics
160 (2012) 2681-2693.
-
The total chromatic number of split-indifference graphs
Discrete Mathematics
312 (2012) 2690-2693
(with
Christiane Neme Campos,
Raphael Machado,
Célia Mello).
-
Complexity separating
classes for edge-colouring and total-colouring
Journal of the Brazilian Computer Society
17 (2011) 281-285
(with
Raphael Machado).
-
Total-chromatic
number of unichord-free graphs
Discrete Applied Mathematics
159 (2011) 1851-1864
(with
Raphael Machado).
-
On the forbidden
induced subgraph sandwich problem
Discrete Applied Mathematics
159 (2011) 1717-1725
(with
Simone Dantas,
Murilo V. G. Da Silva,
Rafael B. Teixeira).
-
The chain graph
sandwich problem
Annals of Operations Research
188 (2011) 133-139
(with
Simone Dantas,
Martin Charles Golumbic,
Sulamita Klein,
Frédéric Maffray).
-
A decomposition for total-colouring partial-grids and list-total-colouring
outerplanar graphs
Networks
57 (2011) 261-269
(with
Raphael Machado).
-
Complexity dichotomy on partial
grid recognition
Theoretical Computer Science
412 (2011) 2370-2379
(with
Vinícius Gusmão P. de Sá,
Guilherme Fonseca,
Raphael Machado).
-
Transitive
orientations in bull-reducible Berge graphs
Discrete Applied Mathematics
159 (2011) 561-573
(with
Frédéric Maffray,
Cláudia R. Villela Maciel).
-
The external
constraint 4 nonempty part sandwich problem
Discrete Applied Mathematics
159 (2011) 661-673
(with
Rafael B. Teixeira,
Simone Dantas).
-
Chromatic index of
graphs with no cycle with a unique chord
Theoretical Computer Science
411 (2010) 1221-1234
(with
Raphael Machado,
Kristina Vuskovic).
-
Unitary toric classes,
the reality and desire diagram, and sorting by transpositions
SIAM Journal on Discrete Mathematics
24 (2010) 792-807
(with
Rodrigo Hausen,
Luerbio Faria,
Luis Antonio B. Kowada).
-
The polynomial
dichotomy for three nonempty part sandwich problems
Discrete Applied Mathematics
158 (2010) 1286-1304
(with
Rafael B. Teixeira,
Simone Dantas).
-
2K2 vertex-set
partition into nonemptyparts
Discrete Mathematics
310 (2010) 1259-1264
(with
Simone Dantas,
Elaine Eschen,
Luerbio Faria,
Sulamita Klein).
-
Decompositions for
edge-coloring join graphs and cobipartite graphs
Discrete Applied Mathematics
158 (2010) 1336-1342
(with
Raphael Machado).
-
On maximizing
clique, clique-Helly and hereditary clique-Helly induced subgraphs
Discrete Applied Mathematics
158 (2010) 1279-1285
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
Enclosing weighted
points with an almost-unit ball
Information Processing Letters
109 (2009) 1216-1221
(with
Guilherme Fonseca).
-
Hamiltonian
paths in odd graphs
Applicable Analysis and Discrete Mathematics
3 (2009) 386-394
(with
Luerbio Faria,
Guilherme Fonseca,
Leticia Rodrigues Bueno).
-
Skewness,
splitting number and vertex deletion of some toroidal meshes
Ars Combinatoria
92 (2009) 53-65
(with
Luerbio Faria,
Candido F. Xavier de Mendonça
Neto,
Jorge Stolfi).
-
The complexity of
clique graph recognition
Theoretical Computer Science
410 (2009) 2072-2083
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
Helly property, clique graphs, complementary graph classes,
and sandwich problems
Journal of the Brazilian Computer Society
14 (2008) 45-52
(with
Mitre C. Dourado,
Priscila Petito,
Rafael B. Teixeira).
-
An improved upper bound on the crossing number of the hypercube
Journal of Graph Theory
59 (2008) 145-161
(with
Luerbio Faria,
Ondrej Sykora,
Imrich Vrto).
-
A new quantum algorithm
to solve the minimum searching problem
International Journal of Quantum Information
6 (2008) 427-436
(with
Luis Antonio B. Kowada,
Carlile Lavor,
Renato Portugal).
-
On the complexity of
the sandwich problems for strongly chordal graphs and chordal bipartite
graphs
Theoretical Computer Science
381 (2007) 57-67
(with
Luerbio Faria,
R. Sritharan,
Sulamita Klein).
-
On the generation of
bicliques of a graph
Discrete Applied Mathematics
155 (2007) 1826-1832
(with
Vania Dias,
Jayme
Szwarcfiter).
-
Cycles
and asteroidal sets in loop graphs
Actas de la Academia Nacional de Ciencias, Argentina
13 (2007) 41-49
(with
Liliana Alcon,
Márcia R. Cerioli,
João Meidanis
and
Marisa Gutierrez).
-
Tree loop
graphs
Discrete Applied Mathematics, Computational Molecular Biology Series,
Issue V
155 (2007) 686-694
(with
Liliana Alcon,
Márcia R. Cerioli,
João Meidanis
and
Marisa Gutierrez).
-
Reversible Karatsuba's algorithm
Journal of Universal Computer Science
12 (2006) 499-511
(with
Luis Antonio B. Kowada,
Renato Portugal).
-
The
pair completion algorithm for the homogeneous set sandwich problem
Information Processing Letters
98 (2006) 87-91
(with
Claudson Bornstein,
Vinicius G. P. de Sá).
-
On maximum planar
induced subgraphs
Discrete Applied Mathematics
154 (2006) 1774-1782
(with
Luerbio Faria,
Sylvain
Gravier,
Candido F. Xavier de Mendonça
Neto,
Jorge Stolfi).
-
The sandwich problem
for cutsets: clique cutset, k-star cutset
Discrete Applied Mathematics
154 (2006) 1791-1798
(with
Rafael B. Teixeira).
-
Algorithms
for the homogeneous set sandwich problem
Algorithmica
46 (2006) 149-180
(with
Guilherme Fonseca,
Vinicius G. P. de Sá,
Jeremy Spinrad).
-
A characterization
of P4-comparability graphs
Discrete Mathematics
306 (2006) 2461-2472
(with
Chinh T. Hoang
and
Frédéric Maffray).
-
Extended skew
partition problem
Discrete Mathematics
306 (2006) 2438-2449
(with
Simone Dantas,
Sylvain
Gravier
and
Sulamita Klein).
-
Generating
bicliques of a graph in lexicographic order
Theoretical Computer Science
337 (2005) 240-248
(with
Vania Dias,
Jayme
Szwarcfiter).
-
The non
planar vertex deletion of Cn x Cm
Ars Combinatoria
76 (2005) 3-28
(with
Jorge Stolfi,
Candido F. Xavier de Mendonça Neto,
and
Luerbio Faria).
-
The perfection and recognition of bull-reducible Berge graphs
RAIRO-Theoretical Informatics and Applications
39 (2005) 145-160
(with
Hazel Everett,
Sulamita Klein,
Bruce Reed).
-
Finding H-partitions efficiently
RAIRO-Theoretical Informatics and Applications
39 (2005) 133-144
(with
Simone Dantas,
Sylvain
Gravier
and
Sulamita Klein).
-
Note on the homogeneous
set sandwich problem
Information Processing Letters
93 (2005) 75-81
(with
Vinicius G. P. de Sá).
-
Optimizing
bull-free perfect graphs
SIAM Journal on Discrete Mathematics
18 (2004) 226-240
(with
Frédéric Maffray).
-
On decision and
optimization (k,l)-graph sandwich problems
Discrete Applied Mathematics
143 (2004) 155-165
(with
Luerbio Faria
and
Simone Dantas).
-
Stable skew partition
problem
Discrete Applied Mathematics
143 (2004) 17-22
(with
Simone Dantas,
Sylvain
Gravier,
Sulamita Klein,
Bruce Reed).
-
On the complexity of the approximation of nonplanarity parameters for cubic graphs
Discrete Applied Mathematics
141 (2004) 119-134
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça Neto).
-
Kinetic hanger
Information Processing Letters
89 (2004) 151-157
(with
Guilherme Fonseca
and
Paulo C. P. Carvalho).
-
The stable
marriage problem with restricted pairs
Theoretical Computer Science
306 (2003) 391-405
(with
Vania Dias,
Guilherme Fonseca
and
Jayme Szwarcfiter).
-
Decompositions for the edge colouring of reduced indifference
graphs
Theoretical Computer Science
297 (2003) 145-155
(with
João Meidanis,
Célia Mello,
and
Carmen Ortiz).
-
Kinetic
heap-ordered trees: tight analysis and improved algorithms
Information Processing Letters
85 (2003) 165-169
(with
Guilherme Fonseca).
-
The graph sandwich problem for 1-join composition is NP-complete
Discrete Applied Mathematics
121 (2002) 73-82
(with
Sulamita Klein
and
Kristina Vuskovic).
-
A note on transitive orientations with maximum sets of sources and sinks
Discrete Applied Mathematics
120 (2002) 91-95
(with
Jayme Szwarcfiter,
Célia Mello,
and
John Gimbel).
-
The splitting
number and skewness of Cn x Cm
Ars Combinatoria
63 (2002) 193-205
(with
Érico F. Xavier,
Karl Schaffer,
Jorge Stolfi,
Candido F. Xavier de Mendonça Neto,
and
Luerbio Faria).
-
On the structure of bull-free perfect graphs, 2:
the weakly triangulated case
Graphs and Combinatorics
17 (2001) 435-456
(with
Frédéric Maffray
and
Oscar Porto).
-
Recognition of quasi-Meyniel graphs
Discrete Applied Mathematics
113 (2001) 255-260
(with
Kristina Vuskovic).
-
On Tucker's proof of the strong perfect graph conjecture for
(K4 - e)-free graphs
Discrete Mathematics
232 1-3 (2001) 105-108
(with
Sylvain Gravier
and
Cláudia Linhares Sales).
-
Splitting number is NP-complete
Discrete Applied Mathematics
108 (2001) 65-83
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça Neto).
-
Finding skew partitions efficiently
Journal of Algorithms
37 (2000) 505-521
(with
Sulamita Klein,
Yoshiharu Kohayakawa,
and
Bruce Reed).
-
On Eggleton and Guy conjectured upper bound for the crossing number of the
n-cube
Mathematica Slovaca
50 (2000) 271-287
(with
Luerbio Faria).
-
A class of beta-perfect graphs
Discrete Mathematics 216 (2000) 169-193
(with Kristina Vuskovic).
-
Local conditions for edge-coloring
Journal of Combinatorial Mathematics and Combinatorial Computing
32 (2000) 79-91
(with
João Meidanis
and
Célia Mello).
-
Total chromatic number and chromatic index of dually chordal graphs
Information Processing Letters
70 (1999) 147-152
(with
João Meidanis
and
Célia Mello).
-
Even and odd pairs in comparability and in P4-comparability graphs
Discrete Applied Mathematics 91 (1999) 293-297
(with
Jayme Szwarcfiter,
Célia Mello,
and
John Gimbel).
-
The homogeneous set sandwich problem
Information Processing Letters 67 (1998) 31-35
(with
Hazel Everett,
Sulamita Klein,
and
Márcia R. Cerioli).
-
Sources and sinks in
comparability graphs
Order 14 (1997) 75-83
(with
John Gimbel,
Célia Mello,
and
Jayme Szwarcfiter).
-
On edge-colouring indifference graphs
Theoretical Computer Science 181 (1997) 91-106
(with
João Meidanis
and
Célia Mello).
-
Path parity and perfection
Discrete Mathematics 165/166 (1997) 233-252
(with
Hazel Everett,
Frédéric Maffray,
and
Bruce Reed).
-
On the structure of
bull-free perfect graphs
Graphs and Combinatorics 13 (1997) 31-55
(with
Frédéric Maffray
and
Oscar Porto).
-
The NP-completeness of multi-partite cutset testing
Congressus Numerantium 119 (1996) 217-222
(with
Sulamita Klein).
-
A linear-time algorithm for proper interval graph recognition
Information Processing Letters 56 (1995) 179-184
(with
João Meidanis
and
Célia Mello).
-
A greedy method for edge-colouring odd maximum degree doubly
chordal graphs
Congressus Numerantium 111 (1995) 170-176
(with
João Meidanis
and
Célia Mello).
-
Split-indifference graphs
Investigación Operativa 3 (1993) 61-68
(with
Célia Mello,
Carmen Ortiz,
and
Mónica Villanueva).
-
On transitive orientations with prescribed sources and sinks
Congressus Numerantium 98 (1993) 191-198
(with
Jayme Szwarcfiter
and
Célia Mello).
-
Ordens indiferença
Pesquisa Operacional 11 (1991) 43-47
(with
Jayme Szwarcfiter,
Sulamita Klein,
and
Célia Mello).
Papers in refereed conferences
-
Pebbling in Kneser graphs
Proceedings of LATIN 2024, Lecture Notes in Computer Science
14579 (2024) 46-60
(with Matheus Adauto, Viktoriya Bardenova, Mariana da Cruz, Glenn Hurlbert, Diana Sasaki).
[pdf]
-
Hyper-heuristics with Path Relinking applied to the Generalised Time-Dependent ATSP in air travel
Proceedings of LAGOS 2023, Procedia Computer Science 223 (2023) 35-42
(with Matheus Simões, Laura Bahiense).
[pdf]
-
Parameterized algorithms for Steiner Tree and Dominating Set: bounding the leafage by the vertex leafage
Proceedings of WALCOM 2022, Lecture Notes in Computer Science 13174 (2022) 251-262
(with Raul Lopes, Alexsander Melo, Ana Silva).
[pdf]
-
Maximum cut on interval graphs of interval count four is NP-complete
Proceedings of MFCS 2021, Leibniz International Proceedings in Informatics (2021)
(with Alexsander Melo, Fabiano Oliveira, Ana Silva).
(with Raul Lopes, Alexsander Melo, Ana Silva).
[pdf]
-
On total coloring the direct product of complete graphs
Proceedings of LAGOS 2021, Procedia Computer Science 195 (2021) 306-314
(with D. Castonguay, L. A. B. Kowada, C. S. R. Patrão, D. Sasaki, M. Valencia-Pabon).
[pdf]
-
On the terminal connection problem
Proceedings of SOFSEM 2021, Foundations of Computer Science, Lecture Notes in Computer Science 12607 (2021) 278-292 (with Alexsander A. Melo, Uéverton S. Souza).
[pdf]
-
On the chromatic index of complementary prisms
Proceedings of EUROCOMB 2019, Acta Math. Univ. Comenianae, Vol. LXXXVIII, 3 (2019), pp. 1071-1077
(with Leandro Zatesko, Renato Carmo, André Guedes, Alesom Zorzi, Raphael Machado).
-
Even-power of cycles with many vertices are Type 1 total colorable
Proceedings of LAGOS 2019, Electronic Notes in Theoretical Computer Science
346 (2019) 747-758
(with Alesom Zorzi, Raphael Machado, Uéverton S. Souza).
-
On caterpillars of game chromatic number 4
Proceedings of LAGOS 2019, Electronic Notes in Theoretical Computer Science
346 (2019) 461-472
(with Ana Luísa Furtado, Simone Dantas, Sylvain Gravier).
-
A general method for forbidden induced sandwich problem NP-completeness
Proceedings of LAGOS 2019, Electronic Notes in Theoretical Computer Science
346 (2019) 393-400
(with Simone Dantas, Priscila Petito, Rafael B. Teixeira).
-
The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
Proceedings of LATIN 2018, Lecture Notes in Computer Science
10807 (2018) 1-13
(with Alexandre Abreu, Luís Cunha, Tharso Fernandes, Luis Kowada, Franklin Marquezino, Daniel Posner, Renato Portugal).
- Simple undirected two-commodity integral flow with a unitary demand
Proceedings of LAGOS 2017,
Latin-American Algorithms, Graphs and Optimization Symposium,
Electronic Notes in Discrete Mathematics
625 (2017) 279-284
(with Alexsander A. Melo, Uéverton S. Souza).
-
Using SPQR-trees to speed up algorithms based on 2-cutset decompositions
Proceedings of LAGOS 2015,
Latin-American Algorithms, Graphs and Optimization Symposium,
Electronic Notes in Discrete Mathematics
50 (2015) 169-174
(with
Helio Macedo Filho, Zhentao Li, Raphael Machado, Nicolas Trotignon).
-
A new reversible circuit
synthesis algorithm based on cycle representations of permutations
Proceedings of LAGOS 2015,
Latin-American Algorithms, Graphs and Optimization Symposium,
Electronic Notes in Discrete Mathematics
50 (2015) 187-192
(with
Andre Cunha Ribeiro, Luis A. B. Kowada, Franklin Marquezino).
-
Linear-time approximation algorithms for unit disk graphs
Proceedings of 12th Workshop on Approximation and Online Algorithms WAOA 2014,
Lecture Notes in Computer Science
8952 (2015) 132-143
(with Vinícius Gusmão P. de Sá, Guilherme Fonseca).
-
A faster 1.375-approximation algorithm for sorting by transpositions
Proceedings of 14th Workshop on Algorithms in Bioinformatics WABI 2014,
Lecture Notes in Computer Science,
Sublibrary: Lecture Notes in Bioinformatics
8701 (2014) 26-37
(with Luis Felipe Cunha, Luis A. B. Kowada, Rodrigo Hausen).
-
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
Proceedings of LATIN 2014, Lecture Notes in Computer Science
8392 (2014) 13-23
(with
Raphael Machado,
Helio Macedo Filho).
-
The same upper bound for both: the 2-page and the rectilinear crossing numbers of the n-cube
Proceedings of the 39th International Workshop
on Graph-Theoretic Concepts in Computer Science WG 2013,
Lecture Notes in Computer Science
8165 (2013) 249-260
(with Luerbio Faria, Bruce Richter, Imrich Vrto).
-
On the 1.375-approximation algorithm for sorting by transpositions in O(nlog n) time
Proceedings of Brazilian Symposium on Bioinformatics BSB 2013,
Lecture Notes in Computer Science,
Sublibrary: Lecture Notes in Bioinformatics
8213 (2013) 126-135
(with Luis Felipe Cunha, Luis A. B. Kowada, Rodrigo Hausen).
-
The generalized split probe problem
Proceedings of LAGOS 2013,
Latin-American Algorithms, Graphs and Optimization Symposium, Electronic
Notes in Discrete Mathematics
44 (2013) 39-45
(with
Simone Dantas, Luerbio Faria, Rafael B. Teixeira).
-
On total coloring and equitable total coloring of cubic graphs with large girth
Proceedings of CTW 2013, Cologne-Twente Workshop on Graphs and Combinatorial
Optimization
(with Diana Sasaki, Myriam Preissmann, Simone Dantas, Giuseppe Mazzuoccolo, Vinícius F. Dos Santos)
-
Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
Proceedings of 10th Workshop on Approximation and Online Algorithms
WAOA 2012,
Lecture Notes in Computer Science
7846 (2013) 82-92
(with Vinícius Gusmão P. de Sá, Guilherme Fonseca, Raphael Machado).
-
Transposition diameter and lonely permutations
Proceedings of Brazilian Symposium on Bioinformatics BSB 2012,
Lecture Notes in Computer Science, Sublibrary: Lecture Notes in
Bioinformatics
7409 (2012) 1-12
(with Luis Felipe Cunha, Luis A. B. Kowada, Rodrigo Hausen).
-
Biclique-colouring powers of paths and powers of cycles
Proceedings of CTW 2012, Cologne-Twente Workshop on Graphs and Combinatorial
Optimization
(with
Helio Macedo Filho, Simone Dantas,
Raphael Machado.).
-
Finding Type 2 snarks with squares is not trivial
Proceedings of CTW 2012, Cologne-Twente Workshop on Graphs and Combinatorial
Optimization
(with Diana Sasaki, Myriam Preissmann, Simone Dantas)
-
Clique-colouring and biclique-colouring unichord-free graphs
Proceedings of LATIN 2012, Lecture Notes in Computer Science
7256 (2012) 530-541
(with
Raphael Machado,
Helio Macedo Filho).
-
Split clique graph complexity
Proceedings of WG 2011, Lecture Notes in Computer Science
6986 (2011) 11-22
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
Analysis and implementation of sorting by transpositions using permutation trees
Proceedings of Brazilian Symposium on Bioinformatics BSB 2011,
Lecture Notes in Computer Science, Sublibrary: Lecture Notes in
Bioinformatics
6832 (2011) 42-49
(with
Marcelo P. Lopes, Marilia D. V. Braga, Rodrigo de A. Hausen, Luis Antonio
B. Kowada).
-
Hamiltonian cycles in
Kneser graphs for n=2k+2
Proceedings of LAGOS 2011,
Latin-American Algorithms, Graphs and Optimization Symposium, Electronic
Notes in Discrete Mathematics
37 (2011) 291-296
(with
Leticia Rodrigues Bueno, Luerbio Faria, Candido F. Xavier de Mendonça Neto,
Rodrigo Hausen).
-
On coloring problems of
snark families
Proceedings of LAGOS 2011,
Latin-American Algorithms, Graphs and Optimization Symposium, Electronic
Notes in Discrete Mathematics
37 (2011) 45-50
(with
Diana Sasaki,
Simone Dantas).
-
Bounds on the
transposition distance for lonely permutations
Proceedings of Brazilian Symposium on Bioinformatics BSB 2010,
Lecture Notes in Computer Science, Sublibrary: Lecture Notes in
Bioinformatics
6268 (2010) 35-46
(with
Rodrigo Hausen,
Luis Antonio B. Kowada).
-
Chromatic index of chordless graphs
Proceedings of CTW 2010 Cologne-Twente Workshop on Graphs and Combinatorial
Optimization
(with
Raphael Machado
and
Nicolas Trotignon).
-
On breadth first search and graph diameter bounds
Proceedings of ALIO-INFORMS Joint International Meeting 2010
(with
Raphael Machado).
-
Complexity dichotomy
on degree-constrained VLSI layouts with unit-length edges
Proceedings of ISCO 2010, International Symposium on Combinatorial
Optimization, Electronic Notes in Discrete Mathematics
36 (2010) 391-398
(with
Vinícius Gusmão P. de Sá,
Guilherme Fonseca,
Raphael Machado).
-
Total chromatic
number of {square,unichord}-free graphs
Proceedings of ISCO 2010, International Symposium on Combinatorial
Optimization, Electronic Notes in Discrete Mathematics
36 (2010) 671-678
(with
Raphael Machado).
-
Advances on the list stubborn problem
Proceedings of CATS 2010, Computing: The Australasian Theory Symposium
Brisbane, Australia
(with
Simone Dantas,
Luerbio Faria,
Sulamita Klein,
Loana Tito Nogueira,
Fabio Protti).
-
Edge-colouring subject to local restrictions
Proceedings of Lagos 2009, Latin-American Algorithms,
Graphs and Optimization Symposium
(with
Raphael Machado).
-
Skew partition
sandwich problem is NP-complete
Proceedings of Lagos 2009, Latin-American Algorithms,
Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics
35 (2009) 9-14
(with
Rafael B. Teixeira,
Simone Dantas).
-
NP-completeness of determining the total chromatic number of graphs that
do not contain a cycle with a unique chord
Proceedings of Cologne-Twente Workshop on Graphs and Combinatorial
Optimization 2009
(with
Raphael Machado).
-
Edge-coloring graphs with no cycle with a unique chord
Proceedings of VI ALIO/EURO Workshop on Applied Combinatorial Optimization
(with
Raphael Machado,
Kristina Vuskovic).
-
The external constraint 4 nonempty part sandwich problem
Proceedings of CLAIO 2008
(with
Rafael B. Teixeira,
Simone Dantas).
-
On the
toric graph as a tool to handle the problem of sorting by
transpositions
Proceedings of Brazilian Symposium on Bioinformatics BSB 2008, Lecture
Notes in Computer Science, Sublibrary: Lecture Notes in Bioinformatics
5167 (2008) 79-91
(with
Rodrigo Hausen,
Luerbio Faria,
Luis Antonio B. Kowada).
-
A decomposition for total-coloring graphs of maximum degree 3
Proceedings of Cologne-Twente Workshop 2008
(with
Raphael Machado).
-
On maximizing
clique, clique-Helly, and hereditary clique-Helly induced
subgraphs
Proceedings of Lagos 2007, Latin-American Algorithms,
Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics
30 (2008) 147-152
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
2K2 vertex-set
partition into nonemptyparts
Proceedings of Lagos 2007, Latin-American Algorithms,
Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics
30 (2008) 291-296
(with
Simone Dantas,
Elaine Eschen,
Luerbio Faria,
Sulamita Klein).
-
The polynomial
dichotomy for three nonempty part sandwich problems
Proceedings of Lagos 2007, Latin-American Algorithms,
Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics
30 (2008) 81-86
(with
Rafael B. Teixeira,
Simone Dantas).
-
Sufficient conditions
for a graph to be edge-colorable with maximum degree colors
Proceedings of Lagos 2007, Latin-American Algorithms,
Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics
30 (2008) 69-74
(with
Raphael Machado).
-
Clique graph recognition
is NP-complete
Proceedings of WG 2006, Lecture Notes in Computer Science
4271 (2006) 269-277
(with
Liliana Alcon,
Luerbio Faria,
Marisa Gutierrez).
-
Loop graphs and
asteroidal sets
Proceedings of 7th International Colloquium on Graph Theory, ICGT '05,
Electronic Notes in Discrete Mathematics
22 179-183 (2005)
(with
Liliana Alcon,
Márcia R. Cerioli,
João Meidanis
and
Marisa Gutierrez).
-
Non loop graphs
with induced cycles
Proceedings of Brazilian Symposium on Graphs, Algorithms
and Combinatorics, Electronic Notes in Discrete Mathematics
19 289-295 (2005)
(with
Liliana Alcon,
Márcia R. Cerioli,
João Meidanis
and
Marisa Gutierrez).
-
Tree loop graphs
Proceedings of LACGA 2004, Electronic Notes in Discrete Mathematics
18 17-23 (2004)
(with
Liliana Alcon,
Márcia R. Cerioli,
João Meidanis
and
Marisa Gutierrez).
-
The sandwich problem for cutsets
Proceedings of LACGA 2004,
Electronic Notes in Discrete Mathematics
18 219-225 (2004)
(with
Rafael B. Teixeira).
-
Nonplanar vertex deletion: maximum degree thresholds for NP/Max SNP-hardness and a 3/4-approximation for
finding maximum planar induced subgraphs
Proceedings of LACGA 2004,
Electronic Notes in Discrete Mathematics
18 121-126 (2004)
(with
Jorge Stolfi,
Candido F. Xavier de Mendonça
Neto,
and
Luerbio Faria).
-
On the generation of
bicliques of a graph
Proceedings of CTW 2004, Electronic Notes in Discrete Mathematics
17 123-127 (2004)
(with
Vania Dias,
Jayme
Szwarcfiter).
-
Faster deterministic and randomized algorithms on the Homogeneous Set Sandwich Problem
Proceedings of WEA 2004, Lecture Notes in Computer Science
3059 (2004) 243-252
(with
Guilherme Fonseca,
Vinicius G. P. de Sá,
Jeremy Spinrad).
-
Simple max-cut for split-indifference graphs and graphs with few P4's
Proceedings of WEA 2004, Lecture Notes in Computer Science
3059 (2004) 87-99
(with
Hans L. Bodlaender,
Marisa Gutierrez,
Ton Kloks,
Rolf Niedermeier).
-
An improved upper bound on the crossing number of the
hypercube
Proceedings of WG 2003, Lecture Notes in Computer Science
2880 (2003) 230-236
(with
Luerbio Faria,
Ondrej Sykora
and
Imrich Vrto).
-
On the complexity of (k,l)-graph sandwich problems
Proceedings of WG 2002, Lecture Notes in Computer Science
2573 (2002) 92-101
(with
Luerbio Faria
and
Simone Dantas).
-
Bull-reducible
Berge graphs are perfect
Proceedings of Comb01, EuroConference on Combinatorics, Graph Theory and
Applications,
Electronic Notes in Discrete Mathematics 10 (2001) 1-3
(with
Hazel Everett,
Sulamita Klein,
and
Bruce Reed).
-
Stable marriages
with restricted pairs
Proceedings of Brazilian Symposium on Graphs, Algorithms and
Combinatorics,
Electronic Notes in Discrete Mathematics 7 (2001) 1-4
(with
Vania Felix Dias,
Guilherme Dias da Fonseca,
and
Jayme
Szwarcfiter).
-
On the complexity of the approximation of nonplanarity parameters for
cubic graphs
Proceedings of Brazilian Symposium on Graphs,
Algorithms and Combinatorics,
Electronic Notes in Discrete Mathematics 7 (2001) 1-4
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça
Neto).
-
The graph sandwich
problem for 1-join composition is NP-complete
Proceedings of 6th International Conference on Graph Theory,
Electronic Notes in Discrete Mathematics 5 (2000) 89-92
(with
Sulamita Klein
and
Kristina Vuskovic).
-
Edge colouring reduced
indifference graphs
Proceedings of LATIN 2000,
Lecture Notes in Computer Science 1776 (2000) 145-153
(with
Célia Mello
and
Carmen Ortiz).
-
Finding skew partitions
efficiently
Proceedings of LATIN 2000,
Lecture Notes in Computer Science 1776 (2000) 163-172
(with
Sulamita Klein,
Yoshiharu Kohayakawa,
and
Bruce Reed).
-
Linear-time
algorithms for maximum sets of sources and sinks
Proceedings of 6th Twente Workshop on Graphs and Combinatorial
Optimization, Electronic Notes in Discrete Mathematics
3 230-234 (1999)
(with
John Gimbel,
Célia Mello,
and
Jayme Szwarcfiter).
-
Optimal node-degree bounds for the complexity of nonplanarity parameters
Proceedings of SODA'99,
Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (1999) 887-888
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça Neto).
-
Splitting number is NP-complete
Proceedings of WG'98,
Lecture Notes in Computer Science 1517 (1998) 285-297
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça Neto).
-
The splitting number of the 4-cube
Proceedings of LATIN'98,
Lecture Notes in Computer Science 1380 (1998) 141-150
(with
Luerbio Faria
and
Candido F. Xavier de Mendonça Neto).
-
On the edge-colouring of split graphs
Proceedings of SEMISH 96,
XXIII Seminário Integrado de Software e Hardware, 415-420
(with
João Meidanis
and
Célia Mello).
-
Even pairs and bull-free perfect graphs
Proceedings of VII Quadrennial International Conference on
the Theory and Applications of Graphs,
Edited by Y. Alavi and A. Schwenk,
Volume I, 391-401, Wiley Interscience, 1995.
-
On edge-colouring
indifference graphs
Proceedings of LATIN'95,
Lecture Notes in Computer Science 911 (1995) 286-299
(with
João Meidanis
and
Célia Mello).
Books
Book chapters
-
Total colouring
by C.M.H. de Figueiredo.
In:
L. W. Beineke, M. C. Golumbic, R. J. Wilson (eds.),
Topics in Algorithmic Graph Theory,
Encyclopedia of Mathematics and its Applications,
Cambridge University Press, 2021.
[pdf]
-
Even pairs in bull-reducible graphs
by C.M.H. de Figueiredo, Frédéric Maffray
and
Cláudia R. Villela Maciel.
In:
L. Ramirez-Alfonsin and A. Bondy (eds.),
Trends in Mathematics, Birkhauser Verlag, 2006, pp. 179-195.
[pdf]
-
Even pairs
by
H. Everett, C.M.H. de Figueiredo, C. Linhares Sales, F. Maffray, O. Porto,
B. Reed.
In:
L. Ramirez-Alfonsin and B.A. Reed (eds.),
Perfect Graphs, Wiley, 2001, pp. 67-92.
-
Emparelhamentos em Grafos: Algoritmos e Complexidade
by C.M.H. de Figueiredo and J.L. Szwarcfiter.
In:
XVIII Jornada de Atualização em Informática, SBC, 1999, pp. 127-161.
-
Coloração em Grafos
by C.M.H. de Figueiredo, J. Meidanis, and C. Mello.
In:
XVIII Jornada de Atualização em Informática, SBC, 1997, pp. 1-45.
Outreach