O Repositório será lançado oficialmente no dia 9 de abril de 2025 às 14h30min no miniauditório do Campus Nova Suiça.
 

k-in-a-TREE: an integer programming approach

Página do item simplificado
dc.contributor.advisorSantos, Vinícius Fernandes dos
dc.contributor.advisorLatteshttp://lattes.cnpq.br/6270626469557436
dc.contributor.authorFerreira, Lucas Saldanha
dc.contributor.refereeSantos, Vinícius Fernandes dos
dc.contributor.refereeMelo, Rafael Augusto de
dc.contributor.refereeValle, Cristiano Arbex
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeMartins, Flávio Vinícius Cruzeiro
dc.date.accessioned2025-03-21T20:14:06Z
dc.date.available2025-03-21T20:14:06Z
dc.date.issued2024-10-16
dc.description.abstractChudnovsky e Seymour (2010) propuseram o algoritmo THREE-IN-A-TREE, que resolve o seguinte problema em tempo polinomial: dado um grafo simples e finito e três vértices fixos, verificar se existe uma árvore induzida contendo esses vértices. Neste trabalho, lidamos com uma generalização natural desse problema, denominada k-IN-A-TREE. Este problema pergunta se um grafo contém uma árvore induzida que abrange k vértices predeterminados. Quando k faz parte da entrada, o problema é conhecido por ser NP-completo, se k ≥ 4 é um número fixo, sua complexidade está aberta. Entretanto existem algoritmos eficientes para casos restritos, como grafos livres de garras, grafos com circunferência pelo menos k e grafos cordais. Neste trabalho apresentamos formulações de programação inteira mista para o problema em questão e mostramos que instâncias com até 25.000 vértices podem ser resolvidas em tempo computacional razoável. Também agregamos mais de três anos de tempo computacional em experimentos projetados para explorar quais variáveis impactam o tempo de execução das várias instâncias geradas; essas análises fornecem um perfil para o problema k-IN-A-TREE em sua forma mais genérica. As contribuições deste trabalho incluem demonstrar que o k-IN-A-TREE pode ser eficientemente resolvido usando Programação Linear Inteira (ILP), permitindo a solução de instâncias de tamanhos relativamente grandes. Além disso, apresentamos análise detalhada que foi conduzida para identificar e caracterizar as principais variáveis que influenciam a dificuldade computacional do problema, fornecendo dados valiosos sobre como a estrutura do grafo, tamanho, conectividade dos vértices e a distribuição dos elementos obrigatórios, afetam a dificuldade. Outra contribuição significativa é a demonstração de que o problema pode ser resolvido de forma eficaz em intervalos de tempo que seriam insuficientes para resolver outros problemas combinatórios complexos, como o Problema do Caixeiro Viajante (TSP). Isso destaca a tratabilidade computacional do problema em ambientes com restrições de tempo, onde outros problemas de complexidade semelhante permanecem mais desafiadores. Essas contribuições avançam o entendimento do problema, estabelecendo um novo marco para a habilidade de resolver o problema e abrindo caminho para futuras explorações teóricas e práticas.
dc.description.abstractotherChudnovsky and Seymour (2010) proposed the THREE-IN-A-TREE algorithm, which solves the following problem in polynomial time: given three fixed vertices in a simple finite graph, check whether an induced tree containing these vertices exists. In this paper, we deal with a generalization of this problem, referred henceforth as k-IN-A-TREE. The k-IN-A-TREE asks whether a graph contains an induced tree spanning k given vertices. When k is part of the input, the problem is known to be NP-complete. If k ≥ 4 is a fixed given number, its complexity is an open question, although there are efficient algorithms for restricted cases such as claw-free graphs, graphs with girth at least k, and chordal graphs. We present mixed-integer programming formulations for this problem and show that instances with up to 25,000 vertices can be solved in reasonable computational time. We also aggregate over three years of computational time in experiments designed to explore which variables impact the execution time of the several generated instances; these analyses provide a profile for the k-IN-A-TREE problem in its most generic form. The contributions of this work include demonstrating that the k-IN-A-TREE problem can be efficiently solved using Integer Linear Programming (ILP), allowing for the solution of instances of relatively large sizes. In addition, a detailed analysis was conducted to identify and characterize the key variables influencing the computational hardness of the problem, providing valuable insights into how the graph’s structure, including factors such as size, vertex connectivity, and the distribution of mandatory elements, affects its solvability. Another significant contribution is the demonstration that the problem can be effectively solved within time intervals that would be insufficient for solving other complex combinatorial problems, such as the Traveling Salesman Problem (TSP). This highlights the computational tractability of k-IN-A-TREE in time-constrained environments, where other similarly complex problems remain more challenging. These contributions advance the understanding of the problem setting a new benchmark for its solvability and paving the way for future theoretical and practical explorations.
dc.description.sponsorshipCNPq, CAPES e FAPEMIG
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/878
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectTeoria dos grafos
dc.subjectComputação gráfica
dc.subjectProgramação linear
dc.subjectAlgoritmos
dc.titlek-in-a-TREE: an integer programming approach
dc.typeThesis

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
k-IN-A-TREE AN INTEGER PROGRAMMING.pdf
Tamanho:
5.89 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional