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.

The generation of graphs and networks with specific characteristics is an important line of research with many potential uses, such as testing optimization algorithms in real-world scenarios and studying dynamic processes in networks. However, existing network models often rely on global knowledge of the network structure or fail to simultaneously capture key characteristics of real networks, such as high local clustering, small-world behavior, and long-tailed degree distributions. The goal of this study is to develop an efficient and flexible network-generation algorithm capable of reproducing the structural properties commonly observed in real-world networks using only local information. We will propose and evaluate a locally driven network-generation mechanism designed to produce realistic network topologies while remaining computationally scalable. The study includes a systematic analysis of existing network-generation algorithms, the development of a novel generation method, and an investigation of its ability to control key structural features, including clustering coefficients, average distances, and degree distributions. The resulting algorithm will be extensively evaluated through simulations and comparative analyses against established models and real-world network data. Finally, the developed method is released as an open-source software package to facilitate its adoption, support reproducibility, and strengthen further research.