Celina Miraglia Herrera de Figueiredo Publications

most significant · Lattes cv · Mathematical Reviews · Google Scholar · dblp · orcid

Papers in refereed journals

• 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 C_n x C_m
  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 C_n x C_m
  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 (K₄ - 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

• Introdução aos Algoritmos Randomizados
  by C.M.H. de Figueiredo, M. Lemos, G. D. Fonseca, and V. G. P. Sá. In: XXVI Colóquio Brasileiro de Matemática, IMPA, 2007. 121p. [página do curso]

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

• Revising Johnson's table for the 21st century, FPT News: The Parameterized Complexity Newsletter, apr 2022, pp. 6-7.
• Resolver ou Verificar? Uma pergunta que vale um milhão de dólares, Ciência Hoje, nov 2011, pp. 42-46.

Last update: Mon Nov 4 13:23:06 -03 2024 by celina.