Uma Aproximação FPT Linear para o Problema da Cobertura Mínima por Varredura

• Lehilton Lelis Chaves Pedrosa Unicamp
• Lucas de Oliveira Silva Unicamp

DOI: https://doi.org/10.5753/etc.2026.20210

Resumo

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.

Referências

Cygan, M., Fomin, F. V., Marx, D., Saurabh, S., Kowalik, L., Lokshtanov, D., and Pilipczuk, M. (2015). Parameterized Algorithms. Springer International Publishing, Cham, Switzerland.

de Oliveira Silva, L. (2025). Algorithms for the freeze-tag and related swarm robotics problems. Master’s thesis, Universidade Estadual de Campinas.

Fekete, S. P., Kleist, L., and Krupke, D. (2021). Minimum scan cover with angular transition costs. SIAM Journal on Discrete Mathematics, 35(2):1337–1355.

Krupke, D. M. (2022). Algorithm Engineering for Hard Problems in Computational Geometry. PhD thesis, Technische Universität Braunschweig.

Lutz, H. (1997). Optical communications in space - twenty years of esa effort. Online; acessado em Fevereiro de 2026 [link].