---

Information extracted from Lattes platform

Last update: 2023/06/23

ORCID: https://orcid.org/0000-0002-4608-4559

---

Current projects

2017 a Atual

Algoritmos e complexidade: Convexidade em grafos e outros problemas O problema conhecido como ``P versus NP'' é certamente um dos problemas mais importantes da computação e da matemática. Tal importância se deve do fato de que a maioria dos problemas de decisão já estudados poderem ser classificados como NP-difíceis ou polinomiais. Este projeto visa fornecer dois tipos de contribuições. Inicialmente um dos objetivos deste projeto consiste em classificar novos problemas quanto à sua complexidade. Além disso, uma vez feita esta classificação, algoritmos eficientes para a solução de problemas ou de subproblemas dos problemas abordados compõem a segunda parte das contribuições esperadas. As contribuições esperadas são em problemas relacionados a grafos e, em particular, em problemas relacionados a ao conceito de convexidade em grafos. Integrantes: Vinicius Fernandes dos Santos (coordenador).

2017 a Atual

Algoritmos e complexidade: Convexidade em grafos e outros problemas (FAPEMIG) Integrantes: Vinicius Fernandes dos Santos (coordenador).

Current applied research projects

See all projects in Lattes

---

Recent publications

Articles in journals

A fix-and-optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty
2023. International Transactions in Operational Research.
Disconnected Matchings
2023. THEORETICAL COMPUTER SCIENCE.
Reducing the vertex cover number via edge contractions
2023. JOURNAL OF COMPUTER AND SYSTEM SCIENCES.
Equitable Partition of Graphs into Independent Sets and Cliques
2022. Matemática Contemporânea.
Jayme?s scientific contributions in the area of Convexity in Graphs
2022. CADERNOS DO IME. SÉRIE INFORMÁTICA.
Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and Kernelization
2022. ALGORITHMICA.
Exact Algorithms for Biclique Coloring
2022. Matemática Contemporânea.
Reducing graph transversals via edge contractions
2021. JOURNAL OF COMPUTER AND SYSTEM SCIENCES.
On the proper orientation number of chordal graphs
2021. THEORETICAL COMPUTER SCIENCE.
On the computational complexity of closest genome problems
2020. DISCRETE APPLIED MATHEMATICS.
Dual Parameterization of Weighted Coloring
2020. ALGORITHMICA.
Covering graphs with convex sets and partitioning graphs into convex sets
2020. INFORMATION PROCESSING LETTERS.
Characterizations, probe and sandwich problems on -cographs
2020. DISCRETE APPLIED MATHEMATICS.
Intersection graph of maximal stars
2020. DISCRETE APPLIED MATHEMATICS.
Climbing the Hill with ILP to Grow Patterns in Fuzzy Tensors
2020. INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS.
One-Sided Weak Dominance Drawing
2019. THEORETICAL COMPUTER SCIENCE.
Parameterized Complexity of Equitable Coloring
2019. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE (ONLINE).
Qubit allocation as a combination of subgraph isomorphism and token swapping
2019. Proceedings of the ACM on Programming Languages.
Complexity aspects of the computation of the rank of a graph
2014. Discrete Mathematics and Theoretical Computer Science (Online).
On the Carathéodory number of interval and graph convexities
2013. Theoretical Computer Science.

Papers in conferences

Reducing the Vertex Cover Number via Edge Contractions
2022. International Symposium on Mathematical Foundations of Computer Science (MFCS).
Weighted Connected Matchings
2022. Latin American Symposium on Theoretical Informatics (LATIN 2022).
Kernelization results for equitable coloring
2021. Latin and American Algorithms, Graphs and Optimization Symposium.
Parameterized algorithms for locating-dominating sets
2021. Latin and American Algorithms, Graphs and Optimization Symposium.
On structural parameterizations of the selective coloring problem
2021. Latin and American Algorithms, Graphs and Optimization Symposium.
Disconnected Matchings
2021. International Computing and Combinatorics Conference.
FPT and Kernelization Algorithms for the Induced Tree problem
2021. 12th International Conference on Algorithms and Complexity.
Linear Programming Models for Sequential and Parallel Token Swaps in Graphs
2020. Simpósio Brasileiro de Pesquisa Operacional.
Structural Parameterizations for Equitable Coloring
2020. Latin American Theoretical Informatics Symposium.
Reducing graph transversals via edge contractions
2020. Mathematical Foundations of Computer Science.
UMA FORMULAÇÃO MATEMÁTICA PARA O PROBLEMA DO NÚMERO DE SALTOS ARBÓREO DE UMA ORDEM PARCIAL
2019. Simpósio Brasileiro de Pesquisa Operacional.
Bigfoot Climbing the Hill with ILP to Grow Patterns in Fuzzy Tensors
2019. Proceedings of the 2019 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (EUSFLAT 2019).
Qubit allocation
2018. the 2018 International Symposium.

Extended abstracts in conferences

Emparelhamento Conexo Ponderado é NP-completo
2022. Encontro de Teoria da Computação.
Finura em Grafos Cordais
2022. Encontro de Teoria da Computação.
Problemas de Particionamento de Grafos em Árvores Monocromáticas
2022. Encontro de Teoria da Computação.
Emparelhamento Desconexo é NP-Completo
2021. Encontro de Teoria da Computação.
Sobre o Número de Orientação Própria de Grafos Cordais
2021. Encontro de Teoria da Computação.
Proper Orientations of Chordal Graphs
2020. Encontro de Teoria da Computação.
Equitable Partition of Graphs into Independent Sets and Cliques
2019. IV Encontro de Teoria da Computação.
Coloração equilibrada de grafos n-Star-Clique
2019. IV Encontro de Teoria da Computação.

Abstracts in conferences

Weighted Connected Matchings
2022. Latin American Workshop on Cliques in Graphs (LAWCG).
Chordal Thinness
2022. Latin American Workshop on Cliques in Graphs (LAWCG).
Weighted connected matchings
2022. Latin Ibero-American Conference on Operations Research (CLAIO 2022).
Kernelization lower bounds for Multicolored Independent Set
2020. Latin American Workshop on Cliques in Graphs.
Partitioning Graphs into Monochromatic Trees
2020. Latin American Workshop on Cliques in Graphs.
Some results on Vertex Separator Reconfiguration
2020. Latin American Workshop on Cliques in Graphs.
Swapping Tokens on Graphs
2020. Latin American Workshop on Cliques in Graphs.

See all publications in Lattes

---

Current students

MS

Aline Silva Reis. A definir. Início: 2022. Universidade Federal de Minas Gerais (Orientador principal)
Guilherme Alvarenga Torres. A definir. Início: 2021. Universidade Federal de Minas Gerais (Orientador principal)
Bruno Maletta Monteiro. A definir. Início: 2021. Universidade Federal de Minas Gerais (Orientador principal)
Eder Ferreira de Figueiredo. A definir. Início: 2021. Universidade Federal de Minas Gerais (Orientador principal)
Sarah Rebecca Dias Luiz. Empacotamentos abertos em grafos. Início: 2020. Universidade Federal de Minas Gerais (Orientador principal)

PhD

Aléssio Miranda Júnior. A definir. Início: 2020. Universidade Federal de Minas Gerais (Orientador principal)
Evellyn Soares Cavalcante. Sobre o problema do número de saltos arbóreos. Início: 2019. Universidade Federal de Minas Gerais (Orientador principal)
Lucas Saldanha Ferreira. Formulações e algoritmos para o problema k-em-árvore. Início: 2016. Centro Federal de Educação Tecnológica de Minas Gerais (Orientador principal)

See all students in Lattes

---