Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH
Revista Eletrônica de Iniciação Científica em Computação · 10.07.2026 · 24 · 459-465
DOI: 10.5753/reic.2026.8447 ↗Kurz gefasst
Fachartikel in der Zeitschrift Revista Eletrônica de Iniciação Científica em Computação, online erschienen am 10.07.2026. Verfasst von Lucas Fraga Damasceno und 6 weiteren Autor:innen. Die Arbeit nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Maximum Minimal Set Cover é a variante max-min do clássico problema Set Cover, cujo objetivo é encontrar um set cover minimal de cardinalidade máxima. Este problema generaliza Max Min Vertex Cover e Upper Domination. Embora (Maximum Minimal) Set Cover e (Maximum Minimal) Hitting Set sejam equivalentes sob certos parâmetros, diferenças surgem quando o tamanho do universo, denotado por n, é considerado. Maximum Minimal Hitting Set admite trivialmente um algoritmo em tempo O∗(2n), mas uma análise exaustiva para Maximum Minimal Set Cover demanda tempo O∗(2m), onde m é o número de conjuntos. Como m pode ser muito maior que n, investigamos algoritmos exatos exponenciais em função de n para o problema. Mostramos que Maximum Minimal Set Cover pode ser resolvido em tempo O∗(2n) e que um algoritmo subexponencial de tempo O∗(2o(n)) implicaria a falsidade da ETH. Por fim, generalizamos os resultados anteriores apresentando um algoritmo em tempo O∗ (2k), onde k é o tamanho do vertex cover mínimo do grafo de incidência, além de um limite inferior mais apertado baseado na SETH.
Zitieren
APA
Damasceno, L. F., Mendonça, F. R., Nascimento, V. P. D., Sampaio, C. M., Santos, A. D., Silva, M. M. A. D., & Souza, U. D. S. (2026). Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH. Revista Eletrônica de Iniciação Científica em Computação, 24, 459-465. https://doi.org/10.5753/reic.2026.8447
Vancouver
Damasceno LF, Mendonça FR, Nascimento VPD, Sampaio CM, Santos AD, Silva MMAD, et al. Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH. Revista Eletrônica de Iniciação Científica em Computação. 2026;24:459-465. doi:10.5753/reic.2026.8447
BibTeX
@article{Damasceno2026,
author = {Damasceno, Lucas Fraga and Mendonça, Felipe Ribeiro and Nascimento, Vinicius Prestes do and Sampaio, Cristiane Magarinos and Santos, Alan David and Silva, Marcelo Miguel Alves da and Souza, Ueverton dos Santos},
title = {Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH},
journal = {Revista Eletrônica de Iniciação Científica em Computação},
year = {2026},
volume = {24},
pages = {459--465},
doi = {10.5753/reic.2026.8447}
}
EUVIMED