Uma Aproximação FPT Linear para o Problema da Cobertura Mínima por Varredura - Pedrosa, Lehilton Lelis Chaves; Silva, Lucas de Oliveira (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
O problema da Cobertura Mínima por Varredura (MSC) escalona as comunicações par-a-par em enxames de satélites usando antenas direcionais. Satélites são pontos no espaço Euclidiano e os custos de alinhamento são proporcionais aos ângulos de rotação. O objetivo é minimizar o tempo total necessário para completar as conexões descritas como arestas de um grafo de entrada. Aproximar o MSC por um fator constante é NP-difícil, mesmo no caso 1D; portanto, recorremos uma parametrização pela largura arbórea. Para instâncias 1D, fornecemos um algoritmo exato de tempo FPT linear. Para 2D, introduzimos o ângulo mínimo não nulo de troca entre vizinhos como segundo parâmetro para projetar uma 2-aproximação de tempo FPT linear.