The maximum k-colorable subgraph problem (2024)
- Authors:
- Autor USP: OLIVEIRA, THIAGO LIMA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2024.tde-25082025-111037
- Subjects: FUNÇÃO TETA; PROGRAMAÇÃO MATEMÁTICA; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Conjuntos estáveis; Função theta de Lovász; Lovászs theta function; Programação semidefinida; Semidefinite programming; Stable sets
- Agências de fomento:
- Language: Inglês
- Abstract: O tema principal desta dissertação de mestrado é o estudo do problema do subgrafo máximo k-colorível usando técnicas de teoria poliédrica, relaxações convexas e programação semidefinida. Dado um grafo, deseja-se encontrar o maior subgrafo induzido cujos vértices possam ser coloridos com k cores. No caso k = 1, o problema se torna o clássico problema do conjunto estável máximo. Narasimhan introduziu uma cota superior para este problema, que pode ser computada em tempo polinomial, e que generaliza a função theta de Lovász. Nesta dissertação, revisamos os resultados básicos sobre o problema do conjunto estável máximo e sua relaxação semidefinida, exibimos a cota introduzida por Narasimhan, e desenvolvemos novas conexões baseadas no trabalho de Lovász
- Imprenta:
- Data da defesa: 12.07.2024
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
OLIVEIRA, Thiago Lima. The maximum k-colorable subgraph problem. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/. Acesso em: 26 dez. 2025. -
APA
Oliveira, T. L. (2024). The maximum k-colorable subgraph problem (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/ -
NLM
Oliveira TL. The maximum k-colorable subgraph problem [Internet]. 2024 ;[citado 2025 dez. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/ -
Vancouver
Oliveira TL. The maximum k-colorable subgraph problem [Internet]. 2024 ;[citado 2025 dez. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/
Informações sobre o DOI: 10.11606/D.45.2024.tde-25082025-111037 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
