Graph colorings and digraph subdivisions (2017)
- Authors:
- Autor USP: MOURA, PHABLO FERNANDO SOARES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: TEORIA DOS GRAFOS; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Coloração de grafos; Column generation; Complexidade computacional; Computational complexity; Convex recoloring; Digraph subdivision; Geração de colunas; Graph coloring; Graph orientation; Inapproximability; Inaproximabilidade; Orientação de grafos; Poliedro; Polyhedral study; Recoloração convexa; Subdivisão de digrafos
- Agências de fomento:
- Language: Inglês
- Abstract: O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, osgraus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos
- Imprenta:
- Data da defesa: 30.03.2017
-
ABNT
MOURA, Phablo Fernando Soares. Graph colorings and digraph subdivisions. 2017. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/. Acesso em: 19 abr. 2024. -
APA
Moura, P. F. S. (2017). Graph colorings and digraph subdivisions (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/ -
NLM
Moura PFS. Graph colorings and digraph subdivisions [Internet]. 2017 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/ -
Vancouver
Moura PFS. Graph colorings and digraph subdivisions [Internet]. 2017 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
