Saltar a contenido

Mapa de algoritmos

Todos los algoritmos de esta página calculan lo mismo: los testores típicos de una matriz básica, o sea, sus minimal hitting sets (ver Conceptos básicos). Los que buscan solo los más cortos están en una tabla aparte.

«En el marco» es el nombre con que se corre en experiments/framework/runner.py. Todos están validados por conjunto de reductos contra la referencia independiente.

Todos los reductos

Algoritmo Familia Publicación En el marco Implementación
BR Testores Lias-Rodríguez y Pons-Porrata, 2009 (a través de fast-BR) —
fast-BR Testores Lias-Rodríguez y Sanchez-Diaz, 2013 fastbr Copia corregida del Java original
fast-BR reescrito, 3 modos Ablación propia — br, br-pivot mhs.Br (nuevo)
fast-CT_EXT Testores ver Revisión de testores fastctext Copia corregida del Java original
GCreduct Testores Rodríguez-Diez et al., 2018 (GCreduct) gcreduct Copia corregida del Java original
YYC Testores ver Lefebre-Lobaina y Ruiz-Shulcloper, 2023 yyc Código de Lefebre (MIT)
RegularSearch Testores Lefebre-Lobaina y Ruiz-Shulcloper, 2023 regsearch, regsearch-java Código de Lefebre (MIT) y reescritura mhs.RegSearch
RCC-MAS (constructos) Testores González-Díaz et al., 2025 (RCC-MAS) rccmas, rccmas-printed mhs.RccMas, desde el pseudocódigo
RUNC, RUNC-M Escuela rusa Djukova y Prokofjev, 2014; Djukova y Prokofjev, 2015 ppdual, ppdual-runc, runcm C++ de Prokofyev (MIT); C++ de Nikiforov (sin licencia)
MMCS Minimal hitting sets Murakami y Uno, 2014 mmcs, shd-mmcs mhs.Mmcs (nuevo, desde el artículo); SHD de Uno
RS Minimal hitting sets Murakami y Uno, 2014 rs, shd-rs mhs.Rs (nuevo); SHD de Uno
Motor único Propio — core-<rep>-<row>-<cand> mhs.core, 8 configuraciones (D4)

Fuera de la primera versión: HTC-BDD (Toda), RoPM Pino Gómez et al., 2021 (RoPM) (sin código), MiLIT (sin licencia), FastRS (Lefebre, sin publicar).

Reductos más cortos

Algoritmo Publicación En el marco Implementación
MinReduct ver Rodríguez-Diez et al., 2018 (GCreduct) (mismo grupo) minreduct Copia corregida
sRGA Susmaga (1998), ficha pendiente srga Copia corregida y Srga nuevo
CAMARDF Zhou et al., 2009 (CAMARDF) camardf Camardf en Java
MMCS acotado — mmcs-shortest mhs.Mmcs

Cómo se relacionan

Las tres familias comparten la prueba de fila crítica. Lo que las separa es dónde ramifican y cuándo descartan candidatos. La tabla completa algoritmo × propiedad está en Propiedades de poda, y las equivalencias demostradas en Descubrimientos, D2.