## Publications: |

- C.G. Fernandes and C.N. Lintzmayer, "How heavy independent sets help to find arborescences with many leaves in DAGs", Journal of Computer and System Sciences, v. 135, 158-174, 2023. [DOI]
- S. Ravelo and C.G. Fernandes, "Complexity and approximability of Minimum Path-Collection Exact Covers", Theoretical Computer Science, v. 942, 21-32, 2023. [DOI]
- C.G. Fernandes, J.C. de Pina, J.L. Ramírez Alfonsín, and S. Robins, "Period collapse in Ehrhart quasi-polynomials of {1,3}-graphs", Combinatorial Theory, vol. 2, issue 3, 2022. [DOI] See the arXiv version.
- C.G. Fernandes, C.N. Lintzmayer, and M.C. San Felice, "Leafy spanning k-forests", Journal of Combinatorial Optimization, vol. 44, 934–946, 2022. [DOI]
- C.G. Fernandes and C.N. Lintzmayer, "Leafy Spanning Arborecences in DAGs", Discrete Applied Mathematics, vol. 323, 217-227, 2022. [DOI] See the arXiv version.
- F. Botler, C.G. Fernandes, and J. Gutiérrez, "On Tuza's conjecture for triangulations and graphs with small treewidth", Discrete Mathematics, v. 344 (4), 112281, 2021. [DOI] See the arXiv version.
- C.G. Fernandes, J.C. de Pina, J.L. Ramírez Alfonsín, and S. Robins, "Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon", Discrete & Computational Geometry, 65(1), 227-243, 2021. [DOI] Also in the arXiv.
- M.R. Cerioli, C.G. Fernandes, R. Gómez, J. Gutiérrez, and P. Lima, "Transversals of longest paths", Discrete Mathematics, vol. 343(3), 135-140, 2020. [DOI] Also in the arXiv.
- C.G. Fernandes, C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, "Prices of anarchy of selfish 2D bin packing games". Int. J. of Foundations of Computer Science, vol. 30(3), 355-374, 2019. [DOI] Also in the arXiv.
- C.G. Fernandes, C. Hernández Vélez, J.C. de Pina, and J.L. Ramírez Alfonsín, "Counting Hamiltonian cycles in the matroid basis graph", Graphs and Combinatorics, 35(2), 539-550, 2019. [DOI] [pdf] See also the arXiv version.
- C.G. Fernandes, T.J. Schmidt, and A. Taraz, "On minimum bisection and related cut problems in trees and tree-like graphs", Journal of Graph Theory, v. 89 (2), 2018, 214-245. [DOI] Also in the arXiv.
- C.G. Fernandes, S.P. de Paula, and L.L.C. Pedrosa,
"Improved Approximation Algorithms for Capacitated Fault-Tolerant
*k*-Center", Algorithmica, v. 80 (3), 1041-1072, 2018. [DOI] See the arXiv version. - C.G. Fernandes and R.C.S. Schouery, "Approximation Algorithms for the Max-Buying Problem with Limited Supply", Algorithmica, v. 80 (11), 2973-2992, 2018. [DOI]
- G. Chen, J. Ehrenmuller, C.G. Fernandes, C.G. Heise, S. Shan, P. Yang, and A. Yates, "Nonempty Intersection of Longest Paths in Series-Parallel Graphs", Discrete Mathematics, v. 340, 287-304, 2017. DOI
- C.G. Fernandes, C.E. Ferreira, A.J.P. Franco, and R.C.S. Schouery, "The Envy-Free Pricing Problem, Unit-Demand Markets and Connections with the Network Pricing Problem", Discrete Optimization, v. 22, Part A, 141-161, 2016. [DOI]
- C.G. Fernandes and M. Kiwi, "Repetition-Free Longest Common Subsequence of Random Sequences", Discrete Applied Mathematics, v. 210, 75-87, 2016. [DOI] Also in the arXiv.
- C.G. Fernandes and M.T.I. Oshiro, "Kinetic Clustering of Points on the Line", Theoretical Computer Science, v. 639, 60-71, 2016. [DOI] Also in the arxiv.
- C.G. Fernandes, C. Hernándes-Vélez, O. Lee, and J.C. de Pina, "Spanning Trees with Nonseparating Paths", Discrete Mathematics, v. 339, 365-374, 2016. [DOI] Also in the arXiv.
- C.G. Fernandes, L.A.A. Meira, F.K. Miyazawa, and L.L.C. Pedrosa, "A Systematic Approach to Bound Factor-Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems", Mathematical Programming A, Volume 153, Issue 2, pp 655-685, 2015. [DOI] Also in the arXiv.
- C.G. Fernandes and M. Stein, "Geodesic Stability for Memoryless Binary Long-lived Consensus", Journal of Computer and System Sciences 81 (7), 1210-1220, 2015. [DOI] Also in the arXiv.
- C.G. Fernandes and R.C.S. Schouery, "Second-Price Ad Auctions with Binary Bids and Markets with Good Competition", Theoretical Computer Science, Volumes 540-541, 103-114, 2014. [DOI]
- E.G. Birgin, P. Feofiloff, C.G. Fernandes, E.L. de Melo, M.T.I. Oshiro, and D.P. Ronconi, "A MILP Model for an Extended Version of the Flexible Job Shop Problem", Optimization Letters, v. 8, 1417-1431, 2014. [DOI]
- S.F. de Rezende, C.G. Fernandes, D.M. Martin and Y. Wakabayashi, "Intersecting Longest Paths", Discrete Mathematics, v. 313, p. 1401-1408, 2013. [DOI]
- G. Calinescu, C.G. Fernandes, H. Kaul, and A. Zelikovsky, "Maximum Series-Parallel Subgraph", Algorithmica: Volume 63, Issue 1 (2012), Page 137-157. [DOI]
- E.S. Laber, C.F. Bornstein, and C.G. Fernandes, "Guest Editorial: Special Issue on Latin American Theoretical Informatics Symposium (LATIN)". Algorithmica 59(1): 1-2 (2011).
- J.R. Correa, C.G. Fernandes and Y. Wakabayashi, "Approximating a Class of Combinatorial Problems with Rational Objective Function", Mathematical Programming B, Volume 124, Numbers 1-2, 255-269, 2010. [DOI]
- S.S. Adi, M.D.V. Braga, C.G. Fernandes, C.E. Ferreira, F.H.V. Martinez, M.-F. Sagot, M.A. Stefanes, C. Tjandraatmadja, and Y. Wakabayashi, "Repetition-Free Longest Common Subsequence", Discrete Applied Mathematics 185 (2010), 1315-1324. [DOI]
- C.G. Fernandes, O. Lee and Y. Wakabayashi, "The Minimum Cycle Cover and the Chinese Postman Problems on Mixed Graphs with Bounded Tree-Width", Discrete Applied Mathematics 157 (2009), pp. 272-279. [DOI]
- G. Calinescu and C.G. Fernandes, "On the k-Structure Ratio in Planar and Outerplanar Graphs", Discrete Mathematics and Theoretical Computer Science, Vol 10, 135-148, No 3 (2008). Available here.
- P. Feofiloff, C.G. Fernandes, C.E. Ferreira and J.C. Pina, "Primal-Dual Approximation Algorithms for the Prize-Collecting Steiner Tree Problem", Information Processing Letters, 103(5), 195-202, 2007. [DOI]
- C.G. Fernandes, V. Lacroix and M.-F. Sagot, "Motif Search in Graphs: Application to Metabolic Networks", IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 3, No. 4, pp. 360-368, 2006. [DOI]
- C.G. Fernandes, E. Green and A. Mandel, "From Monomials to Words to Graphs", Journal of Combinatorial Theory Series A, 105 (2004) 185-206. [DOI]
- G. Calinescu, C.G. Fernandes and B. Reed, "Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width", Journal of Algorithms 48 (2), 333-359 (2003). [DOI]
- G. Calinescu, C.G. Fernandes, H. Karloff and A. Zelikovski, "A New Approximation Algorithm for Finding Heavy Planar Subgraphs", Algorithmica (2003) 36: 179-205. [DOI]
- C.G. Fernandes, "A Better Approximation Ratio for the Minimum k-Edge-Connected Spanning Subgraph Problem", Journal of Algorithms 28 (1), 105-124 (1998). [DOI]
- G. Calinescu, C.G. Fernandes, U. Finkler and H. Karloff, "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms 27 (2), 269-302 (1998). [DOI]

- F. Botler, C.G. Fernandes, and J. Gutiérrez, "Independent dominating sets in planar triangulations", EUROCOMB, 2023, to appear.
- C.G. Fernandes, C.N. Lintzmayer, and P.F.S. Moura, "Approximations for the Steiner Multicycle Problem", LATIN 2022, Lecture Notes in Computer Science, vol 13568, 188-203, 2022. [DOI]
- C.G. Fernandes, C.N. Lintzmayer, and M.C. San Felice, "Heavy and leafy trees", CSBC 2022 - ETC VII. [PDF]
- C.G. Fernandes and C.N. Lintzmayer, "Leafy Spanning Arborecences in DAGs", LATIN 2020, Lecture Notes in Computer Science, vol 12118, 50-62, 2021. [DOI]
- C.G. Fernandes and R. Pocai, "Two simplified versions of Red-Blue Facility Location", CSBC 2019 - ETC IV. [DOI]
- F. Botler, C.G. Fernandes, and J. Gutiérrez, "On Tuza's conjecture for triangulations and graphs with small treewidth", LAGOS, Electronic Notes in Theoretical Computer Science, Volume 346, 2019, p. 171-183. [DOI]
- M.R. Cerioli, C.G. Fernandes, O. Lee, C.N. Lintzmayer, G.O. Mota, and C.N. da Silva, "On edge-magic labelings of forests", LAGOS, Electronic Notes in Theoretical Computer Science, Volume 346, 2019, p. 299-307. [DOI]
- M.C. San Felice, C.G. Fernandes, and C.N. Lintzmayer, "The Online Multicommodity Connected Facility Location Problem", In: 15th International Workshop on Approximation and Online Algorithms (WAOA 2017), Lecture Notes in Computer Science, vol 10787, 118-131, 2018. [DOI]
- M.R. Cerioli, C.G. Fernandes, R. Gómez, J. Gutiérrez, and P. Lima, "Transversals of Longest Paths", LAGOS, Electronic Notes in Discrete Mathematics, Volume 62, 135-140, 2017. [DOI]
- C.G. Fernandes and J. Gutiérrez, "Hitting all longest cycles in a graph", ETC II, 2017. [DOI]
- C.G. Fernandes, S.P. de Paula, and L.L.C. Pedrosa, "Improved Approximation Algorithms for Capacitated Fault-Tolerant
*k*-Center". In: 12th Latin American Theoretical Informatics Symposium (LATIN'16), Ensenada, Mexico. Lecture Notes in Computer Science, Volume 9644, 2016, 441-453. [DOI] - C.G. Fernandes and M.T.I. Oshiro, "Trajectory clustering of points in R", LAGOS, Electronic Notes in Discrete Mathematics (ENDM) (2015), pp. 53-58. [DOI]
- C.G. Fernandes, T.J. Schmidt, and A. Taraz, "Approximating Minimum k-Section in Trees with Linear Diameter", LAGOS, Electronic Notes in Discrete Mathematics (ENDM) (2015), pp. 71-76. [DOI]
- C.G. Fernandes, T.J. Schmidt, and A. Taraz, "On Minimum Bisection and Related Partition Problems in Graphs with Bounded Tree Width", EUROCOMB, Electronic Notes in Discrete Mathematics (ENDM) 49 (2015) 481-488. [DOI]
- C.G. Fernandes and R.C.S. Schouery, "Approximation Algorithms for the Max-Buying Problem with Limited Supply", In: 11th Latin American Theoretical Informatics Symposium (LATIN'14), Montevideo, Uruguay. Lecture Notes in Computer Science, Volume 8392, 2014, 707-718. [DOI]
- C.G. Fernandes, C.E. Ferreira, A.J.P. Franco, and R.C.S. Schouery, "Mixed-Integer Program Formulations for the Unit-Demand Envy-Free Pricing Problem", In: 3rd International Symposium on Combinatorial Optimization (ISCO), Lisbon. Lecture Notes in Computer Science, Volume 8596, 2014, 230-241. [DOI]
- C.G. Fernandes, T.J. Schmidt, and A. Taraz, "On the Structure of Graphs with Large Minimum Bisection", EUROCOMB 2013, The Seventh European Conference on Combinatorics, Graph Theory and Applications, CRM Series, Volume 16, 2013, pp 291-296. [DOI]
- C.G. Fernandes, M.T.I. Oshiro, and N. Schabanel. "Dynamic clustering of evolving networks: some results on the line," AlgoTel, pages 1–4, May 2013. [HAL]
- C.G. Fernandes, L.A.A. Meira, F.K. Miyazawa, and L.L.C. Pedrosa, "A systematic approach to bound factor revealing LPs and its application to the Metric and Squared Metric Facility Location Problems", APPROX'12. Lecture Notes in Computer Science, Volume 7408, 2012, 146-157. Also in the arXiv.
- C.G. Fernandes and R.C.S. Schouery, "Second-Price Ad Auctions with Binary Bids and Markets with Good Competition", ISCO. Lecture Notes in Computer Science, Volume 7422, 2012, 439-450.
- S.F. de Rezende, C.G. Fernandes, D.M. Martin, and Y. Wakabayashi, "Intersection of longest paths in a graph", EUROCOMB 2011, in the Electronic Notes in Discrete Mathematics (ENDM) v. 38, p. 743-748.
- C.G. Fernandes and M. Stein, "Stability in geodesics for memoryless binary long-lived consensus", LAGOS, in the Electronic Notes in Discrete Mathematics (ENDM) v. 37, p. 351-356, 2011.
- C.G. Fernandes, C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, "Selfish Square Packing", LAGOS, in the Electronic Notes in Discrete Mathematics (ENDM) v. 37, p. 369-374, 2011.
- G. Calinescu, C.G. Fernandes, and H. Kaul, "Maximum Series-Parallel Subgraph", WG 2009, Lecture Notes in Computer Science, Volume 5911, 2010, 54-65.
- H. Mendes and C.G. Fernandes, "A concurrent implementation of skip graphs", LAGOS. Electronic Notes in Discrete Mathematics, v. 35. p. 263-268, 2009.
- C.G. Fernandes, C.E. Ferreira, C. Tjandraatmadja, and Y. Wakabayashi, "A polyhedral investigation of the LCS problem and a repetition-free variant", In: 8th Latin American Theoretical Informatics Symposium (LATIN'08), Buzios, Brazil. Lecture Notes in Computer Science 4957. E.S. Laber et al. (Eds.): pp. 329-338, 2008.
- S.S. Adi, M.D.V. Braga, C.G. Fernandes, C.E. Ferreira, F.H.V. Martinez, M.-F. Sagot, M.A. Stefanes, C. Tjandraatmadja, and Y. Wakabayashi, "Repetition-free longest common subsequence", LAGOS 2007. Electronic Notes in Discrete Mathematics, Volume 30, 243-248, 2008.
- J.R. Correa, C.G. Fernandes, M. Matamala, and Y. Wakabayashi, "A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs". In: 5th Workshop on Approximation and Online Algorithms (WAOA), 2007, Eilat. Lecture Notes in Computer Science. Berlin: Spring-Verlag, 2008. v. 4927. p. 184-192. [pdf]
- J.R. Correa, C.G. Fernandes and Y. Wakabayashi, "Approximating Rational Objectives is as Easy as Approximating Linear Ones", SWAT 2006, LNCS 4059, 351-362.
- V. Lacroix, C.G. Fernandes and M.-F. Sagot, "Reaction Motifs in Metabolic Networks". In the Fifth Workshop on Algorithms in Bioinformatics (Mallorca, WABI 2005). LNCS 3692, 178-191.
- J. Boyer, C.G. Fernandes, A. Noma and J.C. Pina, "Lempel, Even, and Cederbaum Planarith Method", In the Third International Workshop in Experimental Algorithms (Angra dos Reis, 2004), C. C. Ribeiro and S. L. Martins, Eds., v. 3059 of Lecture Notes in Computer Science. Springer, pp. 129-144. [pdf] Transparencies available in [pdf]. Information on our implementation here.
- G. Calinescu, C.G. Fernandes, I. Mandoiu, A. Olshevsky, K. Yang, and A. Zelikovsky, "Primal-Dual Algorithms for QoS Multimedia Multicast", GLOBECOM 2003. [ps.gz]
- G. Calinescu and C.G. Fernandes, "Multicuts in Unweighted Digraphs with Bounded Degree and Bounded Tree-Width", Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), 2001. Published in Electronic Notes in Discrete Mathematics, Volume 7, 194-197. [ps.gz]
- C.G. Fernandes and T. Nierhoff, "The UPS Problem", 18th International Symposium on Theoretical Aspects of Computer Science (STACS), Dresden, 238-246, Lecture Notes in Computer Science, 2010, Springer, Berlin, 2001. [ps.gz]
- G. Calinescu, C.G. Fernandes and B. Reed, "Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width", In Integer Programming and Combinatorial Optimization (Berlin, 1998), R. E. Bixby and E. A. Boyd and R. Z. Ríos-Mercado, Eds., v.1412 of Lecture Notes in Computer Science. Springer, pp. 137-152. [ps.gz]
- C.G. Fernandes, "A Better Approximation Ratio for the Minimum k-edge-connected Spanning Subgraph Problem", Proc. 8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 629-638, 1997. [ps.gz]
- G. Calinescu and C.G. Fernandes, "Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus", Proc. 2nd Annual International Computing and Combinatorics Conference (COCOON), v.1090 of Lecture Notes in Comput. Science, 152-161, 1996. [ps.gz]
- G. Calinescu, C.G. Fernandes, U. Finkler and H. Karloff, "A Better Approximation Algorithm for Finding Planar Subgraphs", Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 16-25, 1996. [ps.gz]

- C.G. Fernandes e J.C. Pina Jr., Convite à Geometria Computacional, Jornadas de Atualização em Informática, cap. 7, 2009. Site do capítulo.
- G. Calinescu and C.G. Fernandes, Maximum Planar Subgraph (Chapter 10). In: Handbook of Approximation Algorithms and Metaheuristics: Contemporary and Emerging Applications, Volume 2, 2018. Teofilo F. Gonzalez (Org.). Chapman and Hall/CRC Press. (Chapter 56 of the first edition, 2007.)
- M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001.

- C.G. Fernandes and F.C. Noronha, From partial to full retroactivity without the use of a persistent data structure, 2023.
- C.G. Fernandes, C.N. Lintzmayer, and P.F.S. Moura, Approximations for the Steiner Multicycle Problem, 2023.

- C.H. Cardonha, M.K. de Carli Silva and C.G. Fernandes, Computação Quântica: Complexidade e Algoritmos, Relatório Técnico (in Portuguese), 2005. Anais das Jornadas de Iniciação Científica, IMPA, 2004. [ps.gz][pdf]
- J. Ehrenmuller, C.G. Fernandes, and C.G. Heise, "Nonempty Intersection of Longest Paths in Series-Parallel Graphs", 2013, available in the arXiv.
- P. Feofiloff, C.G. Fernandes, C.E. Ferreira and J.C. Pina, "A Note on Johnson, Minkoff and Phillips' Algorithm for the Prize-Collecting Steiner Tree Problem", revised version, 2009. [arXiv:1004.1437v1 [cs.DS]] [pdf][ps.gz]
- P. Feofiloff, C.G. Fernandes, C.E. Ferreira and J.C. Pina, "$O(n^2\log n)$ implementation of an approximation for the Prize-Collecting Steiner Tree Problem", 2002. [pdf] [ps.gz]
- C.G. Fernandes, H. van der Holst and J.C. Pina, "Multilength Single Pair Shortest Disjoint Paths", Technical Report, 2004. [pdf]
- C.G. Fernandes and R. C. S. Schouery, Algoritmos de aproximação e problemas com sequências, Tecnical Report RT-MAC-2009-04, IME-USP (in Portuguese), 2009. [pdf]
- C.G. Fernandes and R. Thomas, "Edge-Coloring Series-Parallel Multigraphs", 2000. Revised version in the arXiv.

**Orcid:** 0000-0002-5259-2859