Cristina Gomes Fernandes

Idiomas

Áreas de atuação

Organização de eventos

Participação em eventos

Participação em bancas

Orientou

Produções bibliográficas

• FERNANDES, C.G. ; MOTA, G. O. ; SANHUEZA-MATAMALA, N. . Separating path systems in complete graphs. RANDOM STRUCTURES & ALGORITHMS , v. 66, p. e70006, 2025.

• FERNANDES, C. G. ; NAIA, T. ; SANTOS, G. ; Stein, M. . Packing large balanced trees into bipartite graphs. DISCRETE MATHEMATICS , v. 348, p. 114641, 2025.

• BOTLER, FÁBIO ; Fernandes, Cristina G. ; GUTIÉRREZ, JUAN . Independent Dominating Sets in Planar Triangulations. ELECTRONIC JOURNAL OF COMBINATORICS , v. 31, p. P2.12, 2024.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. ; MOURA, PHABLO F.S. . Approximations for the Steiner Multicycle problem. THEORETICAL COMPUTER SCIENCE , v. 1020, p. 114836, 2024.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. . How heavy independent sets help to find arborescences with many leaves in DAGs. JOURNAL OF COMPUTER AND SYSTEM SCIENCES , v. 135, p. 158-174, 2023.

• VALDÉS RAVELO, SANTIAGO ; Fernandes, Cristina G. . Complexity and approximability of Minimum Path-Collection Exact Covers. THEORETICAL COMPUTER SCIENCE , v. 942, p. 21-32, 2023.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. ; San Felice, Mário César . Leafy spanning k-forests. JOURNAL OF COMBINATORIAL OPTIMIZATION , v. 44, p. 934-946, 2022.

• Fernandes, Cristina G. ; DE PINA, JOSÉ C. ; RAMÍREZ ALFONSÍN, JORGE LUIS ; ROBINS, SINAI . Period collapse in Ehrhart quasi-polynomials of ({1,3})-graphs. Combinatorial Theory , v. 2, p. #12, 2022.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. . Leafy spanning arborescences in DAGs. DISCRETE APPLIED MATHEMATICS , v. 323, p. 217-227, 2022.

• BOTLER, FÁBIO ; Fernandes, Cristina G. ; GUTIÉRREZ, JUAN . On Tuza?s conjecture for triangulations and graphs with small treewidth. DISCRETE MATHEMATICS , v. 344, p. 112281, 2021.

• Fernandes, Cristina G. ; DE PINA, JOSÉ C. ; RAMÍREZ ALFONSÍN, JORGE LUIS ; ROBINS, SINAI . Cubic Graphs, Their Ehrhart Quasi-Polynomials, and a Scissors Congruence Phenomenon. DISCRETE & COMPUTATIONAL GEOMETRY , v. 65, p. 227-243, 2021.

• CERIOLI, MÁRCIA R. ; FERNANDES, C. G. ; DIAZ, R. G. G. ; GUTIÉRREZ, JUAN ; LIMA, PALOMA T. . Transversals of longest paths. DISCRETE MATHEMATICS , v. 343, p. 111717, 2020.

• FERNANDES, C. G. ; Ferreira, Carlos E. ; Miyazawa, Flávio K. ; Y. WAKABAYASHI . Prices of Anarchy of Selfish 2D Bin Packing Games. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE , v. 30, p. 355-374, 2019.

• Fernandes, Cristina G. ; HERNÁNDEZ-VÉLEZ, CÉSAR ; DE PINA, JOSÉ C. ; RAMÍREZ ALFONSÍN, JORGE LUIS . Counting Hamiltonian Cycles in the Matroid Basis Graph. GRAPHS AND COMBINATORICS , v. 35, p. 539-550, 2019.

• FERNANDES, C. G. ; Schmidt, Tina Janne ; Taraz, Anusch . On minimum bisection and related cut problems in trees and tree-like graphs. JOURNAL OF GRAPH THEORY , v. 89, p. 214-245, 2018.

• Fernandes, Cristina G. ; Schouery, Rafael C. S. . Approximation Algorithms for the Max-Buying Problem with Limited Supply. ALGORITHMICA , v. 80, p. 2973-2992, 2018.

• Fernandes, Cristina G. ; de Paula, Samuel P. ; Pedrosa, Lehilton L. C. . Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. ALGORITHMICA , v. 80, p. 1041-1072, 2018.

• CHEN, GUANTAO ; EHRENMÜLLER, JULIA ; Fernandes, Cristina G. ; HEISE, CARL GEORG ; SHAN, SONGLING ; YANG, PING ; YATES, AMY N. . Nonempty intersection of longest paths in series-parallel graphs. DISCRETE MATHEMATICS , v. 340, p. 287-304, 2017.

• Fernandes, Cristina G. ; FERREIRA, CARLOS E. ; FRANCO, ÁLVARO J.P. ; SCHOUERY, RAFAEL C.S. . The envy-free pricing problem, unit-demand markets and connections with the network pricing problem. Discrete Optimization , v. 22, p. 141-161, 2016.

• Fernandes, Cristina G. ; HERNÁNDEZ-VÉLEZ, CÉSAR ; LEE, ORLANDO ; DE PINA, JOSÉ C. . Spanning trees with nonseparating paths. DISCRETE MATHEMATICS , v. 339, p. 365-374, 2016.

• Fernandes, Cristina G. ; KIWI, MARCOS . Repetition-free longest common subsequence of random sequences. DISCRETE APPLIED MATHEMATICS , v. 210, p. 75-87, 2016.

• Fernandes, Cristina G. ; OSHIRO, MARCIO T.I. . Kinetic clustering of points on the line. THEORETICAL COMPUTER SCIENCE , v. 639, p. 60-71, 2016.

• Fernandes, Cristina G. ; Stein, Maya . Geodesic stability for memoryless binary long-lived consensus. JOURNAL OF COMPUTER AND SYSTEM SCIENCES , v. 81, p. 1210-1220, 2015.

• Fernandes, Cristina G. ; SCHOUERY, RAFAEL C.S. . Second-Price Ad Auctions with Binary Bids and markets with good competition. THEORETICAL COMPUTER SCIENCE , v. 540-541, p. 103-114, 2014.

• BIRGIN, ERNESTO G. ; FEOFILOFF, PAULO ; Fernandes, Cristina G. ; MELO, EVERTON L. ; OSHIRO, MARCIO T. I. ; RONCONI, DÉBORA P. . A MILP model for an extended version of the Flexible Job Shop Problem. Optimization Letters , v. 8, p. 1417-1431, 2014.

• de Rezende, Susanna F. ; Fernandes, Cristina G. ; Martin, Daniel M. ; Wakabayashi, Yoshiko . Intersecting longest paths. DISCRETE MATHEMATICS , v. 313, p. 1401-1408, 2013.

• C'LINESCU, GRUIA ; Fernandes, Cristina G. ; Kaul, Hemanshu ; Zelikovsky, Alexander . Maximum Series-Parallel Subgraph. ALGORITHMICA , v. 63, p. 137-157, 2012.

• Correa, José R. ; Fernandes, Cristina G. ; Wakabayashi, Yoshiko . Approximating a class of combinatorial problems with rational objective function. MATHEMATICAL PROGRAMMING , v. 124, p. 255-269, 2010.

• Adi, Said S. ; Braga, Marília D.V. ; Fernandes, Cristina G. ; FERREIRA, CARLOS E. ; Martinez, Fábio Viduani ; Sagot, Marie-France ; Stefanes, Marco A. ; Tjandraatmadja, Christian ; Wakabayashi, Yoshiko . Repetition-free longest common subsequence. DISCRETE APPLIED MATHEMATICS , v. 158, p. 1315-1324, 2010.

• FERNANDES, C. G. ; LEE, O ; WAKABAYASHI, Y. . Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width. Discrete Applied Mathematics , v. 157, p. 272-279, 2009.

• CALINESCU, G. ; FERNANDES, C. G. . On the k-restricted structure ratio in planar and outerplanar graphs. Discrete Mathematics and Theoretical Computer Science (Online) , v. 10 (3), p. 135-148, 2008.

• FEOFILOFF, P. ; FERNANDES, C. G. ; FERREIRA, C. E. ; PINA, J. . Primal-Dual Approximation Algorithms for the Prize-Collecting Steiner Tree Problem. Information Processing Letters , v. 103, p. 195-202, 2007.

• V. Lacroix ; FERNANDES, C. G. ; M.-F. Sagot . Motif Search in Graphs: Application to Metabolic Networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics , v. 3 (4), p. 360-368, 2006.

• FERNANDES, C. G. ; E.L. Green ; A. Mandel . From Monomials to Words to Graphs. Journal of Combinatorial Theory. Series A , v. 105, p. 185-206, 2004.

• CALINESCU, G. ; FERNANDES, C. G. ; KARLOFF, H. ; ZELIKOVSKY, A. . A New Approximation Algorithm for Finding Heavy Planar Subgraphs. Algorithmica , EUA, v. 36, p. 179-205, 2003.

• CALINESCU, C. ; FERNANDES, C. G. ; REED, B. . Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width. Journal of Algorithms (Print) , EUA, v. 48, n.2, p. 333-359, 2003.

• CALINESCU, C. ; FERNANDES, C. G. ; FINKLER, H. ; KARLOFF, H. . A Better Approximation Algorithm For Finding Planar Subgraphs. Journal of Algorithms (Print) , EUA, v. 27, n.2, p. 269-302, 1998.

• FERNANDES, C. G. . A Better Approximation Ratio For The Minimum k-Edge-Connected Spanning Subgraph Problem. Journal of Algorithms (Print) , EUA, v. 28, n.1, p. 105-124, 1998.

• CARVALHO, M. H. ; CERIOLI, M. R. ; FERNANDES, C. G. ; FERREIRA, C. E. ; FEOFILOFF, P. ; GUIMARAES, K. S. ; MIYAZAWA, F. K. ; PINA, J. ; SOARES, J. ; WAKABAYASHI, Y. . Uma Introdução Sucinta a Algoritmos de Aproximação. 1. ed. Rio de Janeiro: Publicacoes Matematicas, 2001. v. 1. 157p .

• Fernandes, Cristina G. ; Mota, Guilherme Oliveira ; Sanhueza-Matamala, Nicolás . Separating Path Systems in Complete Graphs. In: José A. Soto; Andreas Wiese (eds) LATIN 2024: 16th Latin American Symposium on Theoretical Informatics.. (Org.). Lecture Notes in Computer Science. 1ed.: Springer Nature Switzerland, 2024, v. 14579, p. 98-113.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. ; Moura, Phablo F. S. . Approximations for the Steiner Multicycle Problem. In: Castañeda, A.; Rodríguez-Henríquez, F. (eds) LATIN 2022: 15th Latin American Symposium on Theoretical Informatics.. (Org.). Lecture Notes in Computer Science. 1ed.Cham: Springer International Publishing, 2022, v. 13568, p. 188-203.

• Fernandes, Cristina G. ; Lintzmayer, Carla N. . Leafy Spanning Arborescences in DAGs. In: Kohayakawa Y.; Miyazawa F.K. (eds) LATIN 2020: 14th Latin American Symposium on Theoretical Informatics.. (Org.). Lecture Notes in Computer Science. 1ed.Suíça: Springer International Publishing, 2020, v. 12118, p. 50-62.

• San Felice, Mário César ; Fernandes, Cristina G. ; Lintzmayer, Carla Negri . The Online Multicommodity Connected Facility Location Problem. Lecture Notes in Computer Science. 1ed.: Springer International Publishing, 2018, v. 10787, p. 118-131.

• Fernandes, Cristina G. ; de Paula, Samuel P. ; Pedrosa, Lehilton L. C. . Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. In: 12th Latin American Theoretical Informatics Symposium (LATIN). (Org.). Lecture Notes in Computer Science. 1ed.: Springer Berlin Heidelberg, 2016, v. 9644, p. 441-453.

• Fernandes, Cristina G. ; Ferreira, Carlos E. ; Franco, Álvaro J. P. ; Schouery, Rafael C. S. . The Envy-Free Pricing Problem and Unit-Demand Markets. In: In: 3rd International Symposium on Combinatorial Optimization (ISCO). (Org.). Lecture Notes in Computer Science. 1ed.: Springer International Publishing, 2014, v. , p. 230-241.

• Fernandes, Cristina G. ; Schouery, Rafael C. S. . Approximation Algorithms for the Max-Buying Problem with Limited Supply. In: In: 11th Latin American Theoretical Informatics Symposium (LATIN). (Org.). Lecture Notes in Computer Science. 1ed.: Springer Berlin Heidelberg, 2014, v. , p. 707-718.

• Fernandes, Cristina G. ; Schmidt, Tina Janne ; Taraz, Anusch . On the structure of graphs with large minimum bisection. The Seventh European Conference on Combinatorics, Graph Theory and Applications. 1ed.: Scuola Normale Superiore, 2013, v. , p. 291-296.

• Fernandes, Cristina G. ; Meira, Luís A. A. ; Miyazawa, Flávio K. ; Pedrosa, Lehilton L. C. . A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems. In: 15th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). (Org.). Lecture Notes in Computer Science. 1ed.: Springer Berlin Heidelberg, 2012, v. , p. 146-157.

• Fernandes, Cristina G. ; Schouery, Rafael C. S. . Second-Price Ad Auctions with Binary Bids and Markets with Good Competition. In: 2nd International Symposium on Combinatorial Optimization (ISCO). (Org.). Lecture Notes in Computer Science. 1ed.: Springer Berlin Heidelberg, 2012, v. , p. 439-450.

• FERNANDES, C. G. ; PINA, J. . Convite à Geometria Computacional. In: André Ponce de Leon F. de Carvalho, USP (coordenador); Tomasz Kowaltowski, IC/UNICAMP (co-coordenador). (Org.). JAI - XXVIII Jornadas de Atualização em Informática. : , 2009, v. XXVIII, p. 331-380.

• CALINESCU, G. ; FERNANDES, C. G. . Maximum Planar Subgraph. In: Teofilo F. Gonzalez. (Org.). Handbook of Approximation Algorithms And Metaheuristics. 1ed.Boca Raton: Chapman and Hall/CRC Press, 2007, v. 10, p. 1-1434.

• CALINESCU, G. ; FERNANDES, C. G. ; KAUL, H. . Maximum Series-Parallel Subgraph. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science, 2010, Montpellier. Lecture Notes in Computer Science. Berlim: Springer-Verlag, 2010. v. 5911. p. 54-65.

• CORREA, J. ; FERNANDES, C. G. ; M. Matamala ; WAKABAYASHI, Y. . A 5/3-approximation for finding spanning trees with many leaves in cubic graphs. In: 5th Workshop on Approximation and Online Algorithms (WAOA), 2008, Eilat. Lecture Notes in Computer Science. Berlin: Spring-Verlag, 2008. v. 4927. p. 184-192.

• FERNANDES, C. G. ; FERREIRA, C. E. ; TJANDRAATMADJA, C. ; WAKABAYASHI, Y. . A polyhedral investigation of the LCS problem and a repetition-free variant. In: 8th Latin American Theoretical Informatics Symposium (LATIN), 2008, Búzios. Lecture Notes in Computer Science, 2008. v. 4957. p. 329-338.

• CORREA, J. ; FERNANDES, C. G. ; WAKABAYASHI, Y. . Approximating Rational Objectives is as Easy as Approximating Linear Ones. In: X Scandinavian Workshop on Algorithm Theory (SWAT), 2006, Riga. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2006. v. 4059. p. 351-362.

• V. Lacroix ; FERNANDES, C. G. ; M.-F. Sagot . Reaction motifs in metabolic networks. In: 5th Workshop on Algorithms in Bioinformatics - WABI 2005, 2005, Eivissa. Lecture Notes in Computer Science. Berlin: Springer Verlag, 2005.

• J.M. Boyer ; FERNANDES, C. G. ; A. Noma ; PINA, J. . Lempel, Even, and Cederbaum planarity method. In: III Workshop on Efficient and Experimental Algorithms, 2004, Angra dos Reis. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2004. v. 3059. p. 129-144.

• CALINESCU, C. ; FERNANDES, C. G. . Multicuts in Unweighted Digraphs with Bounded Degree and Bounded Tree-Width. In: Brazilian Symposium on Graphs, Algorithms and Combinatorics, 2001, Fortaleza, Ceara, Brazil. Eletronic Notes in Discrete Combinatorics - Proceedings of the GRACO, 2001. v. 7. p. 194-197.

• FERNANDES, C. G. ; NIERHOFF, T. . The UPS Problem. In: International Symposium in Theoretical Aspects of Computer Science (STACS), 2001, Dresden (Alemanha). Series: Lecture Notes in Computer Science.. Heidelberg: Springer-Verlag, 2001. v. 2010. p. 247-258.

• CALINESCU, G. ; FERNANDES, C. G. ; REED, B. . Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width. In: IPCO, 1998, Houston - EUA. PROCEEDINGS OF THE 6TH CONFERENCE ON INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION. HOUSTON - EUA, 1998. v. 6. p. 137-152.

• FERNANDES, C. G. . A Better Approximation Ratio For The Minimum k-Edge-Connected Spanning Subgraph Problem. In: 8TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1997, New Orleans - EUA. PROCEEDINGS OF THE 8TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS. NEW ORLEANS - EUA, 1997. v. 8. p. 629-638.

• CALINESCU, G. ; FERNANDES, C. G. ; FINKLER, U. ; KARLOFF, H. . A Better Approximation Algorithm For Finding Planar Subgraphs. In: 7TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, Atlanta - EUA. PROCEEDINGS OF THE 7TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS. ATLANTA - EUA, 1996. v. 7. p. 16-25.

• CALINESCU, G. ; FERNANDES, C. G. . Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus. In: COCOON, 1996, Hong Kong. PROCEEDINGS OF THE 2ND ANNUAL INTERNATIONAL COMPUTING AND COMBINATORICS CONFERENCE. HONG KONG, 1996. v. 2. p. 152-161.

• BOTLER, F. H. ; FERNANDES, C. G. ; LINTZMAYER, C. N. ; LOPES, R. A. ; MISHRA, S. ; NETTO, B. L. ; SAMBINELLI, M. . Immersions of large cliques in graphs with independence number 2 and bounded maximum degree. In: European Conference onCombinatorics, Graph Theory and Applications, 2025, Budapeste. Proceedings of the 13th European Conference onCombinatorics, Graph Theory and Applications, 2025.

• BOTLER, F. H. ; COUTO, Y. S. ; FERNANDES, C. G. ; FIGUEIREDO, E. F. ; GOMEZ, R. ; dos SANTOS, V. F. ; SATO, C. M. . Extremal problems on forest cuts and acyclic neighborhoods in sparse graphs. In: European Conference on Combinatorics, Graph Theory and Applications, 2025, Budapeste. Proceedings of the 13th European Conference onCombinatorics, Graph Theory and Applications, 2025.

• FERNANDES, C. G. ; HOPPEN, C. ; KONTOGEORGIOU, G. ; MOTA, G. O. ; PENG, D. . Separating path systems for 2-degenerate graphs. In: European Conference on Combinatorics, Graph Theory and Applications, 2025, Budapeste. Proceedings of the 13th European Conference onCombinatorics, Graph Theory and Applications, 2025.

• BOTLER, F. H. ; Fernandes, Cristina G. ; GUTIERREZ, J. . Independent dominating sets in planar triangulations. In: European Conference on Combinatorics, Graph Theory and Applications, 2023, Praga. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, 2023. p. 163-168.

• CERIOLI, M. R. ; Fernandes, Cristina G. ; O. Lee ; LINTZMAYER, C. N. ; MOTA, G. O. ; SILVA, C. N. . On Edge-magic Labelings of Forests. In: X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2019, Belo Horizonte. Electronic Notes in Theoretical Computer Science, 2019. v. ENTCS1. p. 299-307.

• BOTLER, F. H. ; FERNANDES, C. G. ; GUTIERREZ, J. . On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth. In: X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2019, Belo Horizonte. Electronic Notes in Theoretical Computer Science, 2019. v. 18878. p. 171-183.

• CERIOLI, M. R. ; Fernandes, Cristina G. ; GOMEZ, R. ; GUTIERREZ, J. ; LIMA, P. T. . Transversals of Longest Paths. In: IX Latin and American Algorithms, Graphs and Optimization (LAGOS), 2017, Marseille, França. Electronic Notes in Discrete Mathematics (DOI: 10.1016/j.endm.2017.10.024), 2017. v. 62. p. 135-140.

• Fernandes, Cristina G. ; Schmidt, Tina Janne ; Taraz, Anusch . On Minimum Bisection and Related Partition Problems in Graphs with Bounded Tree Width. In: EUROCOMB, 2015, Bergen, Norway. Electronic Notes in Discrete Mathematics (DOI:10.1016/j.endm.2015.06.067), 2015. v. 49. p. 481-488.

• Fernandes, Cristina G. ; OSHIRO, M. T. I. . Trajectory clustering of points in R. In: VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2015, Fortaleza. Electronic Notes in Discrete Mathematics (DOI:10.1016/j.endm.2015.07.010), 2015. p. 53-58.

• Fernandes, Cristina G. ; Schmidt, Tina Janne ; Taraz, Anusch . Approximating Minimum k-Section in Trees with Linear Diameter. In: VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2015, Fortaleza. Electronic Notes in Discrete Mathematics (DOI:10.1016/j.endm.2015.07.013), 2015. p. 71-76.

• Fernandes, Cristina G. ; Ferreira, Carlos E. ; MIYAZAWA, F. K. ; Wakabayashi, Yoshiko . Selfish Square Packing. In: VI Latin-American Algorithms, Graphs and Optimization Symposium, 2011, Bariloche. Electronic Notes in Discrete Mathematics. v. 37. p. 369-374.

• Fernandes, Cristina G. ; Stein, Maya . Stability in geodesics for memoryless binary long-lived consensus. In: VI Latin-American Algorithms, Graphs and Optimization Symposium, 2011, Bariloche, Argentina. Electronic Notes in Discrete Mathematics. v. 37. p. 351-356.

• de Rezende, S.F. ; Fernandes, Cristina G. ; Martin, D.M. ; WAKABAYASHI, Y. . Intersection of Longest Paths in a Graph. In: The Sixth European Conference on Combinatorics, Graph Theory and Applications, 2011, Budapeste. Electronic Notes in Discrete Mathematics (DOI:10.1016/j.endm.2011.10.024). Berlim: Elsevier, 2011. v. 38. p. 743-748.

• Mendes, Hammurabi ; Fernandes, Cristina G. . A Concurrent Implementation of Skip Graphs. In: V Latin-American Algorithms, Graphs and Optimization Symposium, 2009, Gramado, Brasil. Electronic Notes in Discrete Mathematics. v. 35. p. 263-268.

• Adi, S.S. ; BRAGA, M.D.V. ; FERNANDES, C. G. ; FERREIRA, C. E. ; MARTINEZ, F.H.V. ; M.-F. Sagot ; STEFANES, M. A. ; TJANDRAATMADJA, C. ; WAKABAYASHI, Y. . Repetition-free longest common subsequence. In: IV Latin American Algorithms, Graphs, and Optimization Symposium, 2008, Puerto Varas, Chile. Electronic Notes in Discrete Mathematics, 2008. v. 755. p. 243-248.

• CALINESCU, G. ; FERNANDES, C.G. ; MANDOIU, I.I. ; OLSHEVSKY, A. ; YANG, K. ; ZELIKOVSKY, A. . Primal-dual algorithms for QoS multimedia multicast. In: GLOBECOM '03. IEEE Global Telecommunications Conference, 2003, San Francisco. GLOBECOM '03. IEEE Global Telecommunications Conference (IEEE Cat. No.03CH37489). v. 2003. p. 3631.

• FEOFILOFF, P. ; FERNANDES, C. G. ; FERREIRA, C. E. ; PINA, J. . A Note on Johnson, Minkoff and Phillips' Algorithm for the Prize-Collecting Steiner Tree Problem 2006 (Relatório técnico arquivado).

• CARDONHA, C. H. ; FERNANDES, C. G. ; SILVA, M. K. C. . Computação Quântica: Complexidade e Algoritmos 2005 (Relatório técnico arquivado).

• FERNANDES, C. G. ; PINA, J. ; H. van der Holst . Multilength Single Pair Shortest Disjoint Paths. São Paulo: Universidade de São Paulo, 2004 (Relatório técnico arquivado).

• FERNANDES, C. G. ; A. Mandel ; E.L. Green . From monomials, to words to graphs 2003 (Relatório técnico arquivado).

• FEOFILOFF, P. ; FERNANDES, C. G. ; FERREIRA, C. E. ; PINA, J. . O(n^2 log n) implementation of an approximation for the Prize-Collecting Steiner Tree Problem 2002 (Relatório técnico arquivado).

• FERNANDES, C. G. ; THOMAS, R. . Edge-Coloring Series-Parallel Multigraphs 2000 (Relatório técnico arquivado).

Projetos de pesquisa

• 2025 - Atual

  Energy Efficiency in Distributed Computing, Descrição: Designing energy-efficient distributed algorithms has garnered significant interest within the distributed computing community, resulting in a substantial number of publications on this topic in recent years. The primary objective of these works is to develop algorithms that solve fundamental problems in distributed computing while optimizing energy efficiency. The initiative we present here focuses on joint research, underpinning its guidelines with a strong emphasis on collaborative knowledge. In technical terms, the natural way to save energy is to allow each agent of a system the possibility of switching off its communication devices. The state in which the agent is online is known as the awake state. In the sleeping state, an agent does not receive, listen, or send messages. It is important to note that being idle and just listening consumes nearly as much energy as sending or receiving messages. In other words, to save energy, agents must be completely offline. This complicates the design of algorithms as messages sent to a node in the sleeping state are lost. Scheduling the rounds in which a node should alternate between sleeping and awake states becomes the central challenge in algorithm design for the sleeping model. We aim to promote student training through research internships and potential co-supervision by team members from different institutions. We intend to merge specialized knowledge to forge significant advancements in the field, leading to top-tier publications.. , Situação: Em andamento; Natureza: Pesquisa. , Alunos envolvidos: Mestrado acadêmico: (2) Doutorado: (5) . , Integrantes: Cristina Gomes Fernandes - Coordenador / Kiwi, Marcos - Integrante / Guilherme O. Mota - Integrante / Fábio H. Botler - Integrante / Yan Soares Couto - Integrante / Pedro Montealegre - Integrante / Lelia Blin - Integrante / Pierre Fraigniaud - Integrante., Financiador(es): Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Cooperação.

• 2024 - Atual

  Problemas de particionamento e conectividade na era dos dados: algoritmos e desafios computacionais, Projeto certificado pelo(a) coordenador(a) Flávio Keidi Miyazawa em 14/01/2025., Descrição: Nos problemas de otimização combinatória, o objetivo é encontrar soluções ótimas que satisfaçam múltiplos requisitos. As soluções são discretas e enumeráveis, mas em grande quantidade, impossibilitando uma busca exaustiva. Problemas clássicos como clusterização, conectividade e roteamento são bem estudados, porém o crescente volume de dados impõe novos desafios com restrições adicionais. Por exemplo, enquanto problemas de particionamento são resolvidos tipicamente por algoritmos clássicos para k-means ou k-center, agora precisamos também que cada cluster mantenha uma proporção mínima de representação social (veja uma ampla discussão em www.fairclustering.com). Em problemas de corte e conectividade, já não basta ter conexão, mas garantir interconexão mesmo na presença de falhas. Em problemas de logística e roteamento, é preciso tomar decisões cada vez mais integradas sobre grandes volumes de dados e com grande importância econômica (e.g., apenas no Brasil, de acordo com a CNT, o custo logístico supera 12 do PIB, podendo chegar a um trilhão de reais). Na grande maioria das vezes, as decisões acima estão associadas a problemas de otimização NP-difíceis e as restrições adicionais tornam esses problemas ainda mais difíceis computacionalmente. Neste projeto, objetivamos investigar aspectos práticos e teóricos de problemas de empacotamento, particionamento e classificação e de problemas de conexidade e roteamento de redes, por meio de abordagens que incluem algoritmos de aproximação, algoritmos parametrizados e programação linear inteira, bem como estudar aspectos relacionados da teoria dos grafos que modelam e sustentam esses problemas e algoritmos. Algoritmos para os problemas propostos são essenciais em muitas áreas e as contribuições teóricas que advirão deste estudo trarão avanços na área. A equipe tem experiência na área e em problemas correlatos e poderá contribuir desenvolvendo soluções inovadoras. (Projeto Universal CNPq - Processo: 404315/2023-2). , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Flávio Keidi Miyazawa - Coordenador / Yoshiko Wakabayashi - Integrante / Lehilton L. C. Pedrosa - Integrante / Renzo Gómez - Integrante / Carla N. Lintzmayer - Integrante / VALDÉS RAVELO, SANTIAGO - Integrante / Phablo F. S. Moura - Integrante / Uéverton Souza - Integrante / Hugo Kooki Kasuya Rosado - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2020 - 2023

  Problemas Extremais e Estruturais em Teoria dos Grafos, Descrição: Este é um projeto de pesquisa para a chamada conjunta de propostas entre a Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), Brasil, e a Comisión Nacional de Investigación Científica y Tecnológica (CONICYT), Chile. As equipes brasileira e chilena têm trabalhado em Combinatória e Teoria dos Grafos há vários anos. Alguns dos membros brasileiros já colaboraram com alguns dos membros chilenos da equipe. Este pedido conjunto pretende estabelecer e consolidar uma cooperação entre as duas equipes trabalhando de forma colaborativa em problemas importantes das áreas do projeto. As linhas de pesquisa propostas neste projeto pertencem ao campo da teoria dos grafos e suas variantes. Grafos são estruturas matemáticas que têm aplicações em uma variedade de assuntos e problemas do mundo real, que vão desde a ciência da computação passando pela física e por redes sociais. Nosso principal objetivo é estudar grafos do ponto de vista teórico, contribuindo para uma melhor compreensão das leis que regem o comportamento dessas estruturas. O avanço neste objetivo deve fornecer novas estratégias para problemas relacionados, bem como disponibilizar novas técnicas para problemas em diversas áreas de conhecimento. Um estudo de várias técnicas combinatórias e um bom entendimento de propriedades estruturais dos grafos são os pilares deste projeto, que deve conduzir às soluções de problemas relevantes. O presente projeto também contribuirá para o fortalecimento do sistema de inserção nacional e internacional das universidades envolvidas. Observamos que as equipes propostas contêm uma mistura de jovens acadêmicos com excelente desempenho acadêmico e renomados pesquisadores que possuem ampla experiência nos problemas a serem investigados.. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Mestrado acadêmico: (3) Doutorado: (4) . , Integrantes: Cristina Gomes Fernandes - Coordenador / Martin Matamala - Integrante / Yoshiharu Kohayakawa - Integrante / Wakabayashi, Yoshiko - Integrante / Maya Stein - Integrante / José Coelho de Pina - Integrante / Maycon Sambinelli - Integrante / Carla N. Lintzmayer - Integrante / Guilherme O. Mota - Integrante / Tassio Naia dos Santos - Integrante / Gabriel Ferreira Barros - Integrante / Henrique Stagni - Integrante / Paulo Matias da Silva Junior - Integrante / Hiep Han - Integrante / Andrea Jiménez - Integrante / Daniel Quiroz - Integrante / José Zamora - Integrante., Financiador(es): Fundação de Amparo à Pesquisa do Estado de São Paulo - Auxílio financeiro.

• 2019 - 2023

  Estruturas de Dados e Algoritmos, Descrição: Diversos problemas reais podem ser modelados por meio de estruturas discretas, tais como grafos, ou por programas de programação linear inteiros ou mistos. Por exemplo, é possível modelar a relação de parentesco em comunidades indígenas por meio de grafos mistos e, das propriedades destes grafos, extrair informações interessantes sobre o comportamento destas comunidades. Pode-se modelar a dispersão de sementes por aves no meio-ambiente através de um grafo bipartido, e a identificação de padrões repetidos nestes grafos pode melhorar o nosso entendimento de como florestas se regeneram, e eventualmente pode ajudar na identificação de fatores que interferem com essa regeneração. Otimização é uma área que se encontra na intersecção da matemática com a ciência da computação e que vem se desenvolvendo rapidamente desde a descoberta do método simplex para programação linear na década de 1940. Métodos de otimização têm aplicações em diversas áreas, dentre as quais destacamos economia, biologia computacional, estudo de redes sociais, logística, etc.O objetivo principal desse projeto é o estudo de estruturas discretas e a investigação de diversos problemas de otimização, com ênfase no desenvolvimento de técnicas e algoritmos, e no tratamento de questões de natureza teórica a respeito desses problemas e estruturas. Dentre as técnicas que investigaremos destacam-se o uso de algoritmos de aproximação, algoritmos enumerativos, métodos probabilísticos, programação linear mista ou inteira, combinatória poliédrica, e programação semidefinida.. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Mestrado acadêmico: (10) Doutorado: (8) . , Integrantes: Cristina Gomes Fernandes - Coordenador / Carlos Eduardo Ferreira - Integrante / José Coelho de Pina Jr - Integrante / Arnaldo Mandel - Integrante / Marcel K. de Carli Silva - Integrante / Yoshiharu Kohayakawa - Integrante / Daniel Morgato Martin - Integrante / Alexandre da Silva Freire - Integrante / Franco, Álvaro J. P. - Integrante / Yoshiko Wakabayashi - Integrante / Atílio Gomes Luiz - Integrante / Cristiane Maria Sato - Integrante / Gabriel M. Coutinho - Integrante / Karla R. Lima - Integrante / Maycon Sambinelli - Integrante / Sinai Robins - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2014 - 2018

  Estudos Teóricos e Práticos de Problemas e Técnicas de Otimização, Projeto certificado pelo(a) coordenador(a) Yoshiko Wakabayashi em 26/06/2015., Descrição: (Proj. CNPq/Edital Universal 2014) O principal objetivo do projeto é a aplicação de técnicas de otimização a diversos problemas, teóricos e práticos, com destaque ao uso de ferramentas de programação semidefinida, programação mista, combinatória poliédrica e algoritmos de aproximação. Nossas investigações contribuirão para avançar o estado-da-arte em otimização combinatória e em áresa correlatas.. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Integrante / Yoshiko Wakabayashi - Coordenador / Marcel K. de Carli Silva - Integrante / José Coelho de Pina - Integrante / Fernando Mario de Oliveira Filho - Integrante / Alexandre da Silva Freire - Integrante.

• 2013 - 2017

  Estruturas combinatórias, otimização e algoritmos em teoria da computação, Projeto certificado pelo(a) coordenador(a) Carlos Eduardo Ferreira em 07/03/2014., Descrição: Temático FAPESP. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Yoshiko Wakabayashi - Integrante / Yoshiharu Kohayakawa - Integrante / Ferreira, Carlos E. - Coordenador / Débora P. Ronconi - Integrante / Daniel M. Martin - Integrante / Gordana Manic - Integrante / José Coelho de Pina - Integrante / Ernesto Birgin - Integrante / Fernando Mario de Oliveira Filho - Integrante / André Fujita - Integrante / Alexandre da Silva Freire - Integrante / Carlos Hoppen - Integrante.

• 2012 - 2015

  Solução de problemas combinatórios com técnicas de Otimização (CNPq - Universal - Proj. No. 477203/2012-4), Projeto certificado pelo(a) coordenador(a) Carlos Eduardo Ferreira em 07/04/2013., Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Coordenador / Yoshiko Wakabayashi - Integrante / Yoshiharu Kohayakawa - Integrante / Ernesto G. Birgin - Integrante / Débora P. Ronconi - Integrante / Daniel M. Martin - Integrante / Gordana Manic - Integrante / José Coelho de Pina - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2010 - 2012

  Estudos Teóricos e Algorítmicos de Problemas Combinatórios e de Otimização, Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Integrante / José Coelho de Pina Jr - Integrante / José Augusto R. Soares - Integrante / Yoshiko Wakabayashi - Coordenador / Ernesto G. Birgin - Integrante / Débora P. Ronconi - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2010 - 2011

  Generating Operational Level Decision for PSP, Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Mestrado acadêmico: (3) Doutorado: (2) . , Integrantes: Cristina Gomes Fernandes - Coordenador / Paulo Feofiloff - Integrante / Ernesto G. Birgin - Integrante / Débora P. Ronconi - Integrante., Financiador(es): Hewlett-Packard Brasil - Matriz - Auxílio financeiro / Hewlett-Packard - Cooperação.

• 2008 - 2009

  Técnicas de Otimização para Problemas Combinatórios, Descrição: Universal CNPq. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Coordenador.

• 2008 - 2009

  Models and Algorithms for Integrative Biology, Descrição: STIC AmiSud. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Roberto M. Cesar Jr. - Coordenador.

• 2006 - 2009

  Computational biology, algorithmics, combinatorial optimization, Descrição: Equipe Associada INRIA. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Integrante / Yoshiko Wakabayashi - Coordenador.

• 2005 - 2008

  Otimização Discreta e Grafos: Teoria, Algoritmos e Aplicações, Descrição: http://www.ime.usp.br/~yw/prosul/. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Yoshiko Wakabayashi - Coordenador.

• 2005 - 2007

  Packing Problems in Combinatorial Optimization, Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Carlos Eduardo Ferreira - Coordenador.

• 2004 - 2007

  Foundations of Computer Science: Combinatorial Algorithms and Discrete Structures, Descrição: (Projeto Temático ProNEx - FAPESP/CNPq Proc. No. 2003/09925-5). The research proposed under this project focuses on the development of efficient combinatorial algorithms and on the investigation of discrete structures of intrinsic interest, with the global aim of giving support of fundamental nature to computer science (CS). This project's approach is of a classical nature. Of the multiple fronts of CS that try to give support to computationally intense research projects of modern science, this project falls into the mathematical category, attacking algorithmic problems rigorously. The algorithms that are developed are analysed for correctness and computational complexity, and, when, relevant, they are implemented. The main themes that will be considered are the following: 1. Several approaches to the development of algorithms for combinatorial optimization problem; 2. Combinatorial problems from computational biology; 3. The structure of graphs and related objects; 4. Asymptotic properties of combinatorial structures. Each of these themes will be regarded as a subproject within this project, under coordination of one of the senior members of the project. Theme 1 will be coordinated by Yoshiko Wakabayashi (DCC-IME-USP), theme 2 by Carlos Eduardo Ferreira (DCC-IME-USP), theme 3, by Cláudio Leonardo Lucchesi (IC-UNICAMP) and theme 4 by Yoshiharu Kohayakawa (DCC-IME-USP).. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Yoshiharu Kohayakawa - Coordenador.

• 1998 - 2004

  Complexity of Discrete Structures, Descrição: Projeto ProNEx 107/97 - MCT/CNPq. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Cristina Gomes Fernandes - Integrante / Yoshiharu Kohayakawa - Coordenador.

Prêmios