Ver registro no DEDALUS
Exportar registro bibliográfico

Graph colorings and digraph subdivisions (2017)

  • Authors:
  • USP affiliated authors: MOURA, PHABLO FERNANDO SOARES - IME
  • USP Schools: 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
  • 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
  • Acesso online ao documento

    Online access or search this record in

    Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    IME31000072603QA840.T M929g e.2
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MOURA, Phablo Fernando Soares; WAKABAYASHI, Yoshiko. Graph colorings and digraph subdivisions. 2017.Universidade de São Paulo, São Paulo, 2017. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/ >.
    • APA

      Moura, P. F. S., & Wakabayashi, Y. (2017). Graph colorings and digraph subdivisions. 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, Wakabayashi Y. Graph colorings and digraph subdivisions [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/
    • Vancouver

      Moura PFS, Wakabayashi Y. Graph colorings and digraph subdivisions [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: