Problema del subárbol de máxima concordancia

El problema del subárbol de máxima concordancia es cualquiera de varios problemas estrechamente relacionados en la teoría de grafos y la informática . En todos estos problemas se da una colección de árboles. $T_{1},\ldots ,T_{m}$ cada uno contiene $n$ hojas. Las hojas de estos árboles reciben etiquetas de algún conjunto $L$ con $|L|=n$ de modo que ningún par de hojas en el mismo árbol comparta la misma etiqueta, dentro del mismo árbol el etiquetado para cada hoja sea distinto. En este problema se desea encontrar el subconjunto más grande. $L'\subset L$ de tal manera que los subárboles de expansión mínima que contienen las hojas en $L'$ , de $T_{1}\mid S,\ldots ,T_{m}\mid S$ son "iguales" conservando el etiquetado.

Formulaciones

subárbol de acuerdo homeomórfico máximo

Fuente: ^{[ 1 ]}

Esta versión requiere que los subárboles $T_{1}\mid S,\ldots ,T_{m}\mid S$ son homeomorfos entre sí.

Subárbol de acuerdo homeomórfico máximo enraizado

Esta versión es la misma que el subárbol de acuerdo homeomórfico máximo , pero además asumimos que $T_{1},\ldots ,T_{m}$ están enraizados y que los subárboles $T_{1}\mid S,\ldots ,T_{m}\mid S$ contiene el nodo raíz. Esta versión del problema del subárbol de máxima concordancia se utiliza para el estudio de árboles filogenéticos . ^{[ 1 ]} Debido a su estrecha relación con la filogenia, esta formulación es a menudo a lo que se refiere uno cuando se habla del problema del "subárbol de máxima concordancia".

Otras variantes

Existen otras formulaciones, por ejemplo, el subárbol de acuerdo isomorfo máximo (con raíz) ^{[ 1 ]} donde requerimos que los subárboles sean isomorfos entre sí.

Véase también

Minería frecuente de subárboles

Referencias

1 2 3 Amir, A.; Keselman, D. (1997-12-01). "Subárbol de máxima concordancia en un conjunto de árboles evolutivos: métricas y algoritmos eficientes". SIAM Journal on Computing . 26 (6): 1656– 1669. CiteSeerX 10.1.1.133.6891 . doi : 10.1137/S0097539794269461 . ISSN 0097-5397 .

Kao, Ming-Yang; Lam, Tak-Wah; Sung, Wing-Kin; Ting, Hing-Fung (agosto de 2001). "Un algoritmo aún más rápido y unificador para comparar árboles mediante emparejamientos bipartitos desequilibrados". Journal of Algorithms . 40 (2): 212– 233. arXiv : cs/0101010 . doi : 10.1006/jagm.2001.1163 .

[:0-1] 1 2 3 Amir, A.; Keselman, D. (1997-12-01). "Subárbol de máxima concordancia en un conjunto de árboles evolutivos: métricas y algoritmos eficientes". SIAM Journal on Computing . 26 (6): 1656– 1669. CiteSeerX 10.1.1.133.6891 . doi : 10.1137/S0097539794269461 . ISSN 0097-5397 .