Júlio César Silva Araújo

Pós-doutorado

Formação complementar

Idiomas

Áreas de atuação

Organização de eventos

Participação em eventos

Participação em bancas

Orientou

Produções bibliográficas

• ARAÚJO, J. ; BENSMAIL, J. ; CAMPOS, V. ; HAVET, F. ; MAIA, A. K. ; NISSE, N. ; SILVA, A. S. . On Finding the Best and Worst Orientations for the Metric Dimension. ALGORITHMICA , p. 2962-3002, 2023.

• Araújo, Júlio ; BOUGERET, MARIN ; CAMPOS, VICTOR A. ; SAU, IGNASI . Parameterized Complexity of Computing Maximum Minimal Blocking and Hitting Sets. ALGORITHMICA , v. 85, p. 444-491, 2023.

• Araujo, Julio ; CAMPOS, VICTOR ; GIRÃO, DARLAN ; NOGUEIRA, JOÃO ; SALGUEIRO, ANTÓNIO ; SILVA, ANA . On the Hull Number on Cycle Convexity of Graphs. INFORMATION PROCESSING LETTERS , v. 183, p. 106420, 2023.

• Araujo, C. S. ; ARAÚJO, J. ; CEZAR, A. A. ; SILVA, A. S. . Backbone coloring of graphs with galaxy backbones. DISCRETE APPLIED MATHEMATICS , v. 323, p. 2-13, 2022.

• Araújo, Júlio ; BOUGERET, MARIN ; CAMPOS, VICTOR ; SAU, IGNASI . Introducing lop-Kernels: A Framework for Kernelization Lower Bounds. ALGORITHMICA , v. 84, p. 3365-3406, 2022.

• ARAÚJO, J. ; ARRAES, P.S.M. . Hull and geodetic numbers for some classes of oriented graphs. DISCRETE APPLIED MATHEMATICS , v. 323, p. 14-27, 2022.

• Araujo, J. ; CEZAR, A. ; LIMA, C.V.G.C. ; DOS SANTOS, V.F. ; SILVA, A. . On the proper orientation number of chordal graphs. THEORETICAL COMPUTER SCIENCE , v. 888, p. 117-132, 2021.

• ARAÚJO, J. ; CAMPOS, V. A. ; LIMA, C. V. G. C. ; SANTOS, V. F. ; SAU, I. ; SILVA, A. S. . Dual Parameterization of Weighted Coloring. ALGORITHMICA , v. 82, p. 2316-2336, 2020.

• Araújo, Júlio ; CAMPOS, VICTOR A. ; MAIA, ANA KAROLINNA ; SAU, IGNASI ; SILVA, ANA . On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. ALGORITHMICA , v. 82, p. 1616-1639, 2020.

• Araújo, Júlio ; SALES, CLÁUDIA LINHARES ; SAU, IGNASI ; SILVA, ANA . Weighted proper orientations of trees and graphs of bounded treewidth. THEORETICAL COMPUTER SCIENCE , v. 771, p. 39-48, 2019.

• Araújo, Júlio ; BASTE, JULIEN ; SAU, IGNASI . Ruling out FPT algorithms for Weighted Coloring on forests. THEORETICAL COMPUTER SCIENCE , p. 11-19, 2018.

• ARAÚJO, J. ; DUCOFFE, G. ; NISSE, N. ; SUCHAN, K. . On interval number in cycle convexity. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE , v. 20, p. 1, 2018.

• ARAÚJO, J. ; BENEVIDES, F. S. ; CEZAR, A. A. ; SILVA, A. S. . Circular backbone colorings: On matching and tree backbones of planar graphs. DISCRETE APPLIED MATHEMATICS , p. 69-82, 2018.

• Araujo, J. ; HAVET, F. ; SCHMITT, M. . Steinberg-like theorems for backbone colouring. DISCRETE APPLIED MATHEMATICS , v. 245, p. 155-167, 2017.

• Araujo, J. ; GIROIRE, F. ; MOULIERAC, J. ; LIU, Y. ; MODRZEJEWSKI, R. . Energy Efficient Content Distribution. COMPUTER JOURNAL , v. 59, p. 192-207, 2016.

• Araujo, Julio ; Havet, Frédéric ; LINHARES SALES, CLAUDIA ; SILVA, ANA . Proper orientation of cacti. Theoretical Computer Science , p. 14-25, 2016.

• ARAÚJO, J. ; CEZAR, A. A. ; SILVA, A. S. . On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring. JOURNAL OF GRAPH THEORY , p. 808-813, 2016.

• ARAÚJO, J. ; MOREL, G. ; SAMPAIO, L. ; SOARES, R. ; WEBER, V. . Hull number:. Discrete Applied Mathematics , p. 171-175, 2015.

• Araujo, J. ; NISSE, N. ; PERENNES, S. . Weighted Coloring in Trees. SIAM Journal on Discrete Mathematics (Print) , v. 28, p. 2029-2041, 2014.

• Araujo, Julio ; Cohen, Nathann ; DE REZENDE, SUSANNA F. ; Havet, Frédéric ; MOURA, PHABLO F.S. . On the proper orientation number of bipartite graphs. Theoretical Computer Science , v. 566, p. 59-75, 2014.

• Araujo, J. ; Linhares Sales, C. . A Hajós-like theorem for weighted coloring. Journal of the Brazilian Computer Society (Impresso) , v. 19, p. 275-278, 2013.

• Araujo, Julio ; Bermond, Jean-Claude ; DUCOFFE, GUILLAUME . Eulerian and Hamiltonian Dicycles in Directed Hypergraphs. Discrete Mathematics, Algorithms and Applications , v. 06, p. 131030175824005, 2013.

• Araujo, J. ; CAMPOS, V. ; GIROIRE, F. ; NISSE, N. ; SAMPAIO, L. ; SOARES, R. . On the hull number of some graph classes. Theoretical Computer Science , v. 475, p. 1-12, 2013.

• Araujo, J. ; Bermond, J-C. ; GIROIRE, F. ; HAVET, F. ; MAZAURIC, D. ; MODRZEJEWSKI, R. . Weighted improper colouring. Journal of Discrete Algorithms (Print) , v. 16, p. 53-66, 2012.

• Araujo, J. ; Linhares Sales, C. . On the Grundy number of graphs with few ¿s. Discrete Applied Mathematics , v. 160, p. 2514-2522, 2012.

• Araujo, J. ; COHEN, N. ; GIROIRE, F. ; HAVET, F. . Good edge-labelling of graphs. Discrete Applied Mathematics , v. 160, p. 2502-2513, 2012.

• ARAÚJO, J. ; DOURADO, M. ; PROTTI, F. ; SAMPAIO, R. . Uma Introdução à Convexidade em Grafos. 1. ed. Rio de Janeiro: Editora do IMPA, 2023.

• ARAÚJO, J. ; CAMPÊLO, M. ; SOUSA, G. . Métodos para determinação do número de envoltória geodésico de um grafo. In: 50º Simpósio Brasileiro de Pesquisa Operacional, 2018, Rio de Janeiro. Proceedings of the Brazilian Symposium on Operations Research. Rio de Janeiro, Brazil: SOBRAPO, 2018.

• Araujo, J. ; NISSE, N. ; Pérennes, Stephane . Weighted Coloring in Trees. In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014, Lyon. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2014. v. 25. p. 75-86.

• Araujo, Julio ; GIROIRE, FREDERIC ; LIU, YANING ; Modrzejewski, Remigiusz ; MOULIERAC, JOANNA . Energy efficient content distribution. In: ICC 2013 2013 IEEE International Conference on Communications, 2013, Budapest. 2013 IEEE International Conference on Communications (ICC). p. 4233-4238.

• AGARWAL, D. ; ARAÚJO, J. ; CAILLOUET, C. ; CAZALS, F. ; COUDERT, D. ; PERENNES, S. . Connectivity Inference in Mass Spectrometry Based Structure Determination. In: European Symposium on Algorithms, 2013, Sophia Antipolis, France. Lecture Notes in Computer Science, 2013. v. 8125. p. 289-300.

• ARAÚJO, J. ; GIROIRE, F. ; MONTEIRO, J. . Hybrid Approaches for Distributed Storage Systems. In: Fourth International Conference on Data Management in Grid and P2P Systems (Globe 2011), 2011, Toulouse, France. Lecture Notes in Computer Science, 2011. v. 6864. p. 1-12.

• Araújo, Júlio ; Linhares Sales, C. ; SAU, I. . Weighted Coloring on P4-sparse Graphs. In: 11es Journées Doctorales en Informatique et Réseaux, 2010, Sophia Antipolis. Proceedings of JDIR'10, 2010. p. 33-38.

• Araújo, Júlio ; Cohen, Nathann ; Giroire, Frédéric ; Havet, Frédéric . Good edge-labelling of graphs. In: V Latin-American Algorithms, Graphs and Optimization Symposium, 2009, Gramado. Eletronic Notes in Discrete Mathematics. v. 35. p. 275-280.

• Araújo, Júlio César Silva ; Linhares Sales, Cláudia . Grundy number on P4P4-classes?. In: V Latin-American Algorithms, Graphs and Optimization Symposium, 2009, Gramado. Eletronic Notes in Discrete Mathematics. v. 35. p. 21-27.

• ARAÚJO, J. ; Moura, P. ; Campêlo, M. . Sobre a complexidade de coloração mista. In: Encontro Regional de Pesquisa Operacional do Nordeste, 2009, Fortaleza. Anais do Encontro, 2009. p. 1-10.

• ARAÚJO, J. ; Linhares Sales, C. . Teorema de Hajós para Coloração Ponderada. In: XXXIX Simpósio Brasileiro de Pesquisa Operacional - SBPO 2007, 2007, Fortaleza. Anais do Simpósio, 2007. p. 2631-2635.

• ARAÚJO, J. ; MARTINS, A. B. ; SANTOS, M. C. . An asymmetric formulation to the harmonious coloring problem. In: LVI Simpósio Brasileiro de Pesquisa Operacional, 2024, Fortaleza. Anais do Simpósio Brasileiro de Pesquisa Operacional, 2024.

• ARAÚJO, J. ; CAMPÊLO, M. ; SOUSA, G. . Computing the geodesic number of a graph. In: LVI Simpósio Brasileiro de Pesquisa Operacional, 2024, Fortaleza. Anais do Simpósio Brasileiro de Pesquisa Operacional, 2024.

• ARAÚJO, J. ; CEZAR, A. . On (acyclic) proper orientations and the cartesian product. In: VIII Encontro de Teoria da Computação (ETC 2023), 2023, João Pessoa. Anais do VIII Encontro de Teoria da Computação (ETC 2023), 2023. p. 50-54.

• ARAÚJO, J. ; MAIA, A. K. ; MEDEIROS, P. P. ; PENSO, L. . On the hull and interval numbers of oriented graphs. In: XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023), 2023, Huatulco, México. Procedia Computer Science, 2023. v. 223. p. 397-399.

• ARAÚJO, J. ; HAVET, F. ; LINHARES SALES, CLAUDIA ; NISSE, N. ; SUCHAN, K. . Semi-proper orientations of dense graphs. In: XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023), 2023, Huatulco, México. Procedia Computer Science, 2023. v. 223. p. 231-240.

• ARAÚJO, J. ; DOURADO, M. ; PROTTI, F. ; SAMPAIO, R. . Tempo de Iteração e Número de Posição Geral em Convexidade de Grafos. In: LV Simpósio Brasileiro de Pesquisa Operacional, 2023, São José dos Campos. Anais do Simpósio Brasileiro de Pesquisa Operacional. Campinas: Galoá, 2023. v. 55.

• ARAÚJO, J. ; MARTINS, A. B. ; SANTOS, M. C. . Coloração harmoniosa. In: 7º Encontro de Teoria da Computação, 2022, Niterói. Anais do VII Encontro de Teoria da Computação (ETC 2022), 2022. p. 121-124.

• ARAÚJO, J. ; CASTRO, R. ; CEZAR, A. . Galáxias como backbone em colorações backbone. In: VII Encontro de Teoria da Computação, 2022, Niterói. Anais do VII Encontro de Teoria da Computação (ETC 2022), 2022. p. 89-92.

• ARAÚJO, J. ; BOUGERET, M. ; CAMPOS, V. ; SAU, I. . A new framework for kernelization lower bounds: the case of Maximum Minimal Vertex Cover. In: International Symposium on Parameterized and Exact Computation (IPEC), 2021, Lisbon. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2021. v. 214. p. 1-19.

• Araujo, C. S. ; Araujo, J. ; CEZAR, A. A. ; SILVA, A. S. . Backbone Coloring of Graphs with Galaxy Backbones. In: X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), 2019, Belo Horizonte. Electronic Notes in Theoretical Computer Science, 2019. v. 346. p. 53-68.

• Araujo, J. ; ARRAES, P. . Hull and Geodetic Numbers for Some Classes of Oriented Graphs. In: X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), 2019, Belo Horizonte. Electronic Notes in Theoretical Computer Science, 2019. v. 346. p. 77-88.

• ARAÚJO, J. ; CAMPOS, V. ; MAIA, A. K. ; SAU, I. ; SILVA, ANA . On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. In: Latin American Symposium on Theoretical Informatics, 2018, Buenos Aires. Lecture Notes in Computer Science, 2018. v. 10807. p. 66-79.

• ARAÚJO, J. C. ; CAMPOS, V. ; LIMA, C. V. G. C. ; SANTOS, V. F. ; SAU, I. ; SILVA, A. S. . Dual Parametrization of Weighted Coloring. In: 13th International Symposium on Parameterized and Exact Computation, 2018, Helsinki, Finland. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. v. 115. p. 1-14.

• ARAÚJO, J. ; BASTE, J. ; SAU, I. . Ruling out FPT Algorithms for Weighted Coloring. In: IX Latin-American Algorithms, Graphs and Optimization Symposium, 2017, Marselha, França. Eletronic Notes in Discrete Mathematics, 2017. v. 62. p. 195-200.

• ARAÚJO, J. ; HAVET, F. ; SCHMITT, M. . Steinberg-like theorems for backbone colouring. In: VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'15), 2015, Beberibe, Ceará, Brazil. Eletronic Notes in Discrete Mathematics, 2015. v. 50. p. 223-229.

• ARAÚJO, J. ; MOREL, G. ; SAMPAIO, L. ; SOARES, R. ; WEBER, V. . Hull number: P5-free graphs and reduction rules. In: VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2013, Playa del Carmen, Mexico. Eletronic Notes in Discrete Mathematics, 2013. v. 44. p. 67-76.

• Araujo, J. ; CAMPOS, V. ; GIROIRE, F. ; SAMPAIO, L. ; SOARES, R. . On the hull number of some graph classes. In: European Conference on Combinatorics, Graph Theory and Applications, 2011, Budapest. Eletronic Notes in Discrete Mathematics. v. 38. p. 49-55.

• ARAÚJO, J. ; Bermond, J-C. ; GIROIRE, F. ; HAVET, F. ; MAZAURIC, D. ; MODRZEJEWSKI, R. . Weighted Improper Colouring. In: International Workshop on Combinatorial Algorithms (IWOCA), 2011, Victoria, Canada. Lecture Notes in Computer Science, 2011. v. 7056. p. 1-18.

• ARAÚJO, J. ; CASTRO, R. ; TALON, A. . About directed backbone colourings of graphs. In: 11th Latin American Workshop on Cliques in Graphs, 2024, Aquiraz, Brazil. Annals of LAWCG 2024, 2024.

• ARAÚJO, J. ; BOUGERET, M. ; CAMPOS, V. ; SAU, I. . Parameterized complexity of computing maximum minimal blocking and hitting sets. In: 10th Latin American Workshop on Cliques in Graphs, 2022, Curitiba. Annals of the LawCG2022, 2022. p. 83-83.

• ARAÚJO, J. ; CEZAR, A. A. ; LIMA, C. V. G. C. ; SANTOS, V. F. ; SILVA, A. S. . Sobre o número de orientação própria de grafos cordais. In: 6º Encontro de Teoria da Computação, XLI Congresso da Sociedade Brasileira de Computação, 2021, Online. Anais do XLI CSBC, 2021.

• ARAÚJO, J. ; CEZAR, A. A. ; LIMA, C. V. G. C. ; SANTOS, V. F. ; SILVA, A. S. . Proper orientations of chordal graphs. In: 5º Encontro de Teoria da Computação, XL Congresso da Sociedade Brasileira de Computação, 2020, Cuiabá. Anais do XL CSBC, 2020. p. 21-24.

• ARAÚJO, J. ; ARRAES, P. . Número de envoltória em classes de grafos orientados. In: III Encontro de Teoria da Computação (ETC) - Congresso da Sociedade Brasileira de Computação, 2018, Natal. Anais do III Encontro de Teoria da Computação, 2018. p. 77-80.

• ARAÚJO, J. ; Campêlo, M. ; SOUSA, G. . Calculando o número de envoltória nas convexidades P3 e P3*. In: III Encontro de Teoria da Computação (ETC) - Congresso da Sociedade Brasileira de Computação, 2018, Natal. Anais do III Encontro de Teoria da Computação, 2018. p. 21-24.

• ARAÚJO, J. ; Linhares Sales, C. ; SAU, I. ; SILVA, A. S. . Weighted proper orientations of trees and graphs of bounded treewidth. In: VIII Latin American Workshop on Cliques in Graphs, 2018, Rio de Janeiro. Annals of VIII Latin American Workshop on Cliques in Graphs, 2018. p. 72-72.

• Araujo, J. ; Araujo, C. S. ; CEZAR, A. A. . Coloração 2-backbone de grafos periplanares com um emparelhamento como backbone. In: 2° Encontro de Teoria da Computação, 2017, São Paulo. Anais do XXXVII Congresso da Sociedade Brasileira de Computação, 2017. p. 174-177.

• ARAÚJO, J. ; COHEN, N. ; DE REZENDE, S. F. ; HAVET, F. ; Moura, P. . On the proper orientation number of bipartite graphs. In: 9th International colloquium on graph theory and combinatorics, 2014, Grenoble. Conference proceedings, 2014.

• ARAÚJO, J. ; DOURADO, M. ; PROTTI, F. ; SAMPAIO, R. . The iteration time and the general position number in graph convexities. APPLIED MATHEMATICS AND COMPUTATION , 2025.

• ARAÚJO, J. . Da Teoria de Ramsey à Otimização em Grafos. 2019. (Apresentação de Trabalho/Conferência ou palestra).

• ARAÚJO, J. . O mundo colorido pela matemática. 2017. (Apresentação de Trabalho/Conferência ou palestra).

• ARAÚJO, J. . O mundo colorido pela matemática. 2017. (Apresentação de Trabalho/Conferência ou palestra).

• ARAÚJO, J. . Alguns resultados recentes e tendências em Pesquisa Operacional. 2013. (Apresentação de Trabalho/Conferência ou palestra).

Outras produções

Projetos de pesquisa

• 2023 - Atual

  Graphs, Optimization, Combinatorics and Algorithms, Descrição: CAPES/COFECUB 88881.712024/2022-01. Colaboração UFC - Université Côte d'Azur - Université d'Avignon - Université de Montpellier.. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Integrante / Frederic Havet - Integrante / Ignasi Sau - Integrante / Manoel Campêlo - Integrante / Nicolas Nisse - Integrante / Rudini Menezes Sampaio - Integrante / Rafael Castro de Andrade - Integrante / Ana Shirley Ferreira da Silva - Integrante / Fabrício Siqueira Benevides - Coordenador / Ana Karolinna Maia de Oliveira - Integrante / Victor Almeida Campos - Integrante / Marcio Costa Santos - Integrante / Philippe Yves Paul Michelon - Integrante / Pablo Luiz Braga Soares - Integrante / Tatiane Fernandes Figueiredo - Integrante / Rosa Figueiredo - Integrante / Serigne GUEYE - Integrante., Financiador(es): Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Auxílio financeiro.

• 2023 - Atual

  Combinatorial Algorithms for Networking prOblEms (CANOE), Descrição: Équipe Associée INRIA. Colaboração UFC - Université Côte d'Azur. Coordenador francês: Nicolas Nisse.. , Situação: Em andamento; Natureza: Pesquisa. , Alunos envolvidos: Doutorado: (3) . , Integrantes: Júlio César Silva Araújo - Coordenador / Frederic Giroire - Integrante / Frederic Havet - Integrante / Nicolas Nisse - Integrante / Fabrício Siqueira Benevides - Integrante / Ana Karolinna Maia de Oliveira - Integrante / Victor Almeida Campos - Integrante / Jonas Costa - Integrante / Thomas DISSAUX - Integrante / Lucas PICASARRI-ARRIETA - Integrante., Financiador(es): Centre de Recherche Inria Sophia Antipolis - Méditerranée - Auxílio financeiro.

• 2022 - Atual

  Complexidade parametrizada para parâmetros de coloração e convexidade em grafos, Descrição: Bolsa de Produtividade CNPq 313153/2021-3. Este projeto propõe o estudo de parâmetros de otimização em grafos relacionados a problemas em variantes de Coloração de Grafos, assim como a problemas sobre Convexidades em Grafos. Para todos os problemas estudados, haverá um enfoque especial no estudo da Complexidade Parametrizada dos mesmos. Propõe-se tanto o estudo de temas mais teóricos, ligados à ciência básica, como também o estudo de parâmetros em grafos que possuem aplicações práticas e são de interesse social. No contexto de Coloração de Grafos, as variantes que serão abordadas serão: orientações pró- prias, colorações backbone e colorações harmônicas. Com respeito a Convexidade em Grafos, serão estudados os parâmetros número de intervalo, número de envoltória e posto nas convexidades geodé- tica, P3 e P3∗ . Para orientações próprias e colorações backbone, existem várias perguntas em aberto na literatura, sobretudo na determinação de limitantes superiores para os respectivos parâmetros, que serão abordados. Para colorações harmônicas, o objetivo central é preparar um survey sobre o assunto. Para os parâmetros de convexidade supramencionados, será dada ênfase especial ao caso direcionado, pouco estudado na literatura. Uma terceira grande linha de pesquisa deste projeto é o desenvolvimento de um novo framework que interliga as áreas de Complexidade Parametrizada e Algoritmos Aproximativos. Além das contribuições científicas na forma de participação em eventos e publicações de artigos em revistas internacionais, prevê-se também a formação de alunos de graduação e pós-graduação. Além disso, haverá interações com outros grupos de pesquisa no Brasil e no exterior para trabalhar nos temas do projeto.. , Situação: Em andamento; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Coordenador., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Bolsa.

• 2021 - Atual

  Paralelismo e Algoritmos Para Otimização, Combinatória e Complexidade (PAPOCCO), Descrição: FUNCAP [PS1-0186-155.01.00/21] O objetivo do projeto é obtenção de algoritmos e modelos matemáticos para resolução automática de problemas computacionais, incluindo para isso o estudo da complexidade dos problemas, a análise combinatória estrutural das instâncias, bem como criação de ferramentas computacionais para resolução distribuída ou paralela dos mesmos em quantidade massiva de dados. O projeto se concentra em certos problemas combinatórios teóricos de interesse e suas variantes, como coloração de grafos, conectividade em grafos, difusão de informações em redes sociais, jogos multiagentes em grafos, entre outros, visando à obtenção de modelos discretos e contínuos, com aplicações em problemas práticos em áreas como telecomunicações e logística. Ademais, pretende-se pesquisar teoria e técnicas de desenvolvimento de algoritmos para esses problemas de otimização combinatória, produzindo algoritmos exatos, probabilísticos, aproximativos, heurísticas ou algoritmos FPT, usando técnicas de decomposição, particionamento, kernelização e aproximação dos problemas, entre outras. Finalmente, pretende-se pesquisar técnicas de desenvolvimento e implementação de algoritmos concorrentes, paralelos e distribuídos para resolução eficaz de tais problemas em instâncias de grande porte, bem como a aplicação de sistemas de computação paralela desenvolvidos por membros do projeto, como o HPC Shelf. Entre os problemas, destaca-se o Problema de Difusão em Redes Sociais, cujo objetivo é achar o menor número de vértices capazes de difundir uma informação para todo grafo, usando vários modelos distintos de propagação (como P3 ou geodésica). Outros problemas são relacionados à conectividade em grafos: determinar interligações entre vários elementos, como caminho entre dois pontos da cidade ou rede de comunicação entre computadores. Alguns dos problemas, como árvore geradora mínima e fluxo máximo, surgem com restrições adicionais que os tornam computacionalmente difíceis... , Situação: Em andamento; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (15) / Mestrado acadêmico: (10) / Doutorado: (15) . , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Integrante / Ronan Soares - Integrante / Manoel Bezerra Campêlo Neto - Integrante / Rafael Castro de Andrade - Integrante / Ana Shirley Ferreira da Silva - Integrante / Fabrício Siqueira Benevides - Integrante / Francisco Heron de Carvalho Junior - Integrante / Ana Karolinna Maia de Oliveira - Integrante / Rudini Sampaio - Coordenador / Nicolas de Almeida Martins - Integrante / Allberson Bruno de Oliveira Dantas - Integrante / Cenez Araújo de Rezende - Integrante / Tiago Carneiro Pessoa - Integrante., Financiador(es): Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2019 - 2023

  Problemas sobre contagem e sobre parâmetros em colorações de grafos, Descrição: Projeto Universal 437841/2018-9. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Integrante / Victor Campos - Integrante / Rudini Menezes Sampaio - Integrante / Ana Shirley Ferreira da Silva - Integrante / Fabrício Siqueira Benevides - Coordenador / Antônio Josefran Bastos - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2019 - 2021

  Graphs ALgorithms for Optimization Problems - GALOP, Descrição: Projeto CAPES/STIC-AmSud 88881.197438/2018-01. Estudaremos a Complexidade Computacional de vários problemas importantes em redes (roteamento, alocação de recursos, etc.). Focaremos na determinação de propriedades métricas e estruturais e na determinação de parâmetros em redes de larga escala (e.g. redes de transporte ou redes sociais).. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Doutorado: (1) . , Integrantes: Júlio César Silva Araújo - Coordenador / Victor Campos - Integrante / Ronan Soares - Integrante / Rudini Menezes Sampaio - Integrante / Ana Shirley Ferreira da Silva - Integrante / Fabrício Siqueira Benevides - Integrante / Ana Karolinna Maia de Oliveira - Integrante / LINHARES SALES, CLAUDIA - Integrante., Financiador(es): Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Cooperação.

• 2019 - 2021

  Limitantes e complexidade computacional para parâmetros de coloração e convexidade em grafos, Descrição: Projeto relativo à Bolsa Pq - Processo nº 304478/2018-0. Resumo: Este projeto propõe o estudo de vários parâmetros em grafos relacionados a Coloração de Grafos e a Convexidade em Grafos. O problema de Coloração de Grafos possui diversas variações definidas na literatura devido às suas diversas aplicações práticas e às restrições inerentes a cada uma. Estudaremos as variações conhecidas como: Colorações Backbone, Orientações Próprias e Colorações Acíclicas. As duas primeiras já vem sendo estudadas pelo proponente nos últimos anos, enquanto que a última tem sido estudada nos últimos meses e buscará-se obter contribuições significativas nos próximos anos. Já a mais recente área de Convexidade em Grafos, possui diversos parâmetros definidos na literatura e cada um deles pode ser estudado em cada uma das diversas convexidades definidas. Propomos o estudo dos parâmetros número de envoltória, número de intervalo e número de convexidade, nas convexidades geodésica, P 3 e de ciclos. Neste novo projeto, focaremos nossos estudos em grafos direcionados e também trabalharemos nestes parâmetros através do uso de formulações de Programação Linear-Inteira para calcularmos estes parâmetros. Para todos os parâmetros a serem estudados, buscaremos não só encontrar limitantes para os mesmos, como também algoritmos polinomiais, aproximativos e/ou polinomiais a parâmetro fixo (FPT), assim como demonstrações de NP-dificuldade ou de W-dificuldade quando nos restringirmos a classes de grafos.. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Coordenador., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Bolsa.

• 2017 - 2020

  Coloração backbone, coloração gulosa e convexidade cíclica, Situação: Concluído; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Integrante / Leonardo Sampaio - Integrante / Fabrício Siqueira Benevides - Integrante / SILVA, ANA - Coordenador., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2017 - Atual

  Problemas em grafos: complexidade e métodos, Descrição: Funcap/CNPq Pronem PNE-0112-00061.01.00/16. O tema central deste projeto é a resolução computacional eficiente de problemas de otimização combinatória, envolvendo teoria, algoritmos e implementações sequenciais e paralelas, com aplicações. Nesse sentido, as atividades do projeto seguem os três eixos complementares do ParGO que são paralelismo, grafos e otimização. Os problemas investigados nesta proposta são classificados entre os mais difíceis computacionalmente considerando o critério de complexidade de tempo. Com isto, é necessário o estudo estrutural sobre o problema para a obtenção de algoritmos eficientes para instâncias de médio ou grande porte. Uma técnica que pode se mostrar eficiente é o estudo teórico de descrições matemáticas distintas, porém equivalentes para o problema. Tais descrições matemáticas são analisadas, com o objetivo de determinar propriedades estruturais que possam ser, posteriormente, exploradas de forma adequada usando métodos algorítmicos. No âmbito desta proposta, as descrições dos problemas utilizam principalmente Teoria dos Grafos, Teoria Poliédrica e Programação Linear Inteira. Junto com o estudo teórico, realizamos a resolução computacional dos problemas propostos. Dados a dificuldade de resolver tais problemas computacionalmente, utilizamos algumas técnicas para facilitar a obtenção de resultados para instâncias de médio a grande porte. As principais técnicas empregadas são decomposições, relaxações, planos de corte e paralelismo.. , Situação: Em andamento; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (3) / Mestrado acadêmico: (4) / Doutorado: (18) . , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Integrante / Ignasi Sau - Integrante / Ronan Soares - Integrante / Nicolas Nisse - Integrante / Manoel Bezerra Campêlo Neto - Integrante / Rudini Menezes Sampaio - Integrante / Rafael Castro de Andrade - Integrante / Ricardo Cordeiro Corrêa - Integrante / Fabrício Siqueira Benevides - Integrante / Francisco Heron de Carvalho Junior - Integrante / Criston Souza - Integrante / Jayme Luiz Szwarcfiter - Integrante / Ana Karolinna Maia de Oliveira - Integrante / Fábio Carlos Sousa Dias - Integrante / SILVA, ANA - Integrante / Victor Almeida Campos - Coordenador / Frédéric Maffray - Integrante / Mitre Dourado - Integrante / Javier Marenco - Integrante / Tibérius de Oliveira e Bonates - Integrante / Francicleber Martins Ferreira - Integrante / Jefferson de Carvalho Silva - Integrante / Yoshiko Wakabayashi - Integrante / Bruce Reed - Integrante / Nicolas Trotignon - Integrante / Alberto Adasme Soto - Integrante / Pavol Hell - Integrante., Financiador(es): Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2016 - 2018

  Novos parâmetros em Coloração e Convexidade em grafos, Descrição: Projeto relativo a bolsa de produtividade. Se propõe o estudo de dois parâmetros em Coloração de Grafos - a saber: Número Cromático Backbone e Número de Orientação própria - e dos parâmetros número de fecho, número de intervalo e número de convexidade nas Convexidades Geodésica e de Ciclos em grafos.. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Coordenador., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Bolsa.

• 2014 - 2018

  Variações Recentes de Coloração de Grafos, Descrição: O objetivo deste projeto é obtenção de resultados do ponto de vista de Teoria de Grafos e Complexidade Computacional para três variações do problema de Coloração de Grafos. Este problema é um dos mais estudados na literatura sobre Teoria de Grafos, Otimização Combinatória e Complexidade Computacional devido às inúmeras aplicações práticas que esse problema modela, como, por exemplo, problema de Escalonamento de Tarefas, Alocação de Registros de Computadores, Atribuição de Frequências, etc. Entretanto, diversas outras aplicações similares possuem propriedades particulares que não podem ser modeladas pelo problema clássico de Coloração de Grafos. Dessa forma, inúmeras variações desse problema foram definidas e estudadas na literatura. Este é uma área de intensa pesquisa nas últimas décadas. Neste projeto, nos propomos a estudar três dessas variações: Coloração Backbone, b-Coloração e Orientação Própria de Grafos. Todas essas variações foram definidas há não muito tempo - a mais antiga em 1999 - e diversas questões em aberto sobre essas variações ainda precisam ser estudadas. Nós buscaremos tratar algumas dessas questões com o intuito de aprofundar as bases de conhecimento sobre esses três problemas e, consequentemente, sobre o problema de Coloração de Grafos.. , Situação: Concluído; Natureza: Pesquisa. , Integrantes: Júlio César Silva Araújo - Coordenador / Cláudia Linhares Sales - Integrante / Leonardo Sampaio - Integrante / Ana Shirley Ferreira da Silva - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro., Número de produções C, T & A: 12

• 2014 - 2017

  Graphs and AlgorIthms Applied to TelecommunicatiOns (GAIATO), Descrição: This project aims at enhancing and strengthening the existing cooperation between COATI and ParGO research groups. Such a partnership has shown to be very fruitful, as can be infered by a number of joint publications and co-supervisions of students. Problems and applications in graphs have been one of the common interests of the two groups. In the proposed work, we elected some problems in graphs with appplications in telecommunications. Besides being the basis to model several real applications, the studies of these problems are relevant by their own. Recurring issues related to graph problems, such as computational complexity and approximability in arbitrary graphs and specific graph classes, structural properties, decomposition strategies, design of efficient algorithms are only partially established or still undefined for several of the elected problems and variants. Most of the work, even if it cannot be directly applied to solve the applications that motivated it, gives better insight on the practical problems they model. Moreover, the obtained results will lead to publications in international journals as well as communications in conferences in the domain. In order to achieve the scientific goals, our studies may comprise the following aspects: (1) Complexity analysis: knowing if the problem is polynomial, NP-complete, approximable or not determine the type of algorithmes we will design; (2) Structural studies, where we attempt to derive decomposition theorems or intrinsic properties that could help solving the problems; (3) Combinatorial bounds derivation to allow evaluating the quality of partial solutions and establishing approximation ratios for approximation algorithms; (4) Algorithms design and analysis, where several techniques are envisaged as a way of identifying differents aspects of a same problem; (5) Implementation and experimentation, which aims at testing the practical efficiency of the algotihms we design in order to compare them with existing algorithms.. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (2) / Mestrado acadêmico: (3) / Doutorado: (4) . , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Integrante / Manoel Bezerra Campêlo Neto - Coordenador / Rudini Menezes Sampaio - Integrante / Rafael Castro de Andrade - Integrante / Victor de Almeida Campos - Integrante / Ricardo Cordeiro Corrêa - Integrante / Ana Shirley Ferreira da Silva - Integrante / Napoleão Vieira Nepomuceno - Integrante / Fabrício Siqueira Benevides - Integrante., Financiador(es): Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico - Auxílio financeiro.

• 2011 - 2014

  Problemas de coloração e conversão irreversível em grafos, Projeto certificado pelo(a) coordenador(a) Claudia Linhares Sales em 02/05/2014., Descrição: Nesse projeto há dois problemas em foco: o problema de b-coloração de grafos e o problema de conversão irreversível em grafos. O processo de conversão irreversível pode ser usado, por exemplo, para modelar a propagação de opinião, doença ou falhas. Portanto, o mesmo tem sido extensivamente estudado por pesquisadores das mais diversas áreas, sobre diversas perpectivas e sobre vários graus de formalidade matemática, sendo uma importante questão na fronteira científica. Para citar apenas algumas áreas, destacamos sua importância em influência social, redes neurais, redes genéticas, sistemas de imunidade, autômatos celulares, percolação, estratégias de marketing, e especialmente em computação distribuída. Por outro lado, uma aplicação natural para o problema de b-coloração é a de avaliação de heurísticas para coloração de grafos. Além disso, os conceitos também tem sido utilizados em clustering de banco de dados, ou seja em agrupamento automático de dados segundo seu grau de semelhança, bem como no reconhecimento automático de documentos. Outro que o grande número de aplicações, esses problemas possibilitam o estudo e emprego de técnicas sofisticadas de provas em teoria dos grafos, probabilidade e algoritmos que podem ser reutilizadas em problemas semelhantes.. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (6) / Mestrado acadêmico: (3) / Doutorado: (1) . , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Coordenador / Victor de Almeida Campos - Integrante / Ana Shirley Ferreira da Silva - Integrante / Fabrício Siqueira Benevides - Integrante., Financiador(es): Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro., Número de produções C, T & A: 4

• 2011 - 2013

  Paralelismo, Grafos e Otimização, Descrição: O tema deste projeto é a resolução computacional eficiente de problemas de otimização combinatória, envolvendo teoria, algoritmos e implementações sequenciais e paralelas, com aplicações. A pesquisa se desenvolverá em três grandes eixos: (i) Estruturas Matemáticas e Métodos Algorítmicos em Otimização Combinatória; (ii) Aplicações; (iii) Resolução Eficiente de Grandes Instâncias de Problemas. Os principais objetivos científicos são: 1. estabelecer modelos, formulações e propriedades estruturais para de problemas de otimização combinatória, especialmente aqueles definidos sobre conjuntos independentes em grafos e através de fluxos em redes; 2. desenvolver algoritmos exatos e heurísticos eficientes usando técnicas de decomposição, de relaxação linear e Lagrangeana, geração de cortes ou colunas; 3. obter implementações computacionais sequenciais e paralelas capazes de resolver instâncias de tamanho médio para grande desses problemas. O principal objetivo instituciona é consolidar o grupo de pesquisa ParGO nacional e internacionalmente, aumentando a sua inserção no meio acadêmico e a sua relevância para o desenvolvimento da Ciência da Computação no Estado do Ceará. (Proj Aprovado no Edital CNPq/FUNCAP PRONEM 2010 PRN 0040-00040.01.00/10).. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (10) / Mestrado acadêmico: (11) / Doutorado: (7) . , Integrantes: Júlio César Silva Araújo - Integrante / Cláudia Linhares Sales - Integrante / Victor Campos - Integrante / Manoel Bezerra Campêlo Neto - Coordenador / Rudini Menezes Sampaio - Integrante / Rafael Castro de Andrade - Integrante / Ricardo Cordeiro Corrêa - Integrante / Andréa Carneiro Linhares - Integrante / Francisco Heron de Carvalho Junior - Integrante / Criston Souza - Integrante / CARLOS DIEGO RODRIGUES - Integrante., Financiador(es): Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico - Auxílio financeiro / Conselho Nacional de Desenvolvimento Científico e Tecnológico - Auxílio financeiro.