Problema del subárbol de acuerdo máximo

El problema del subárbol de máxima concordancia es cualquiera de varios problemas estrechamente relacionados en teoría de grafos e informática . En todos estos problemas se presenta una colección de árboles , cada uno de los cuales contiene hojas. Las hojas de estos árboles reciben etiquetas de algún conjunto , 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 es distinto. En este problema, a uno le gustaría encontrar el subconjunto más grande tal que los subárboles de extensión mínima que contienen las hojas en , de sean "iguales" preservando al mismo tiempo el etiquetado. ${\displaystyle T_{1},\ldots ,T_{m}}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle |L|=n}$ ${\displaystyle L'\subset L}$ ${\displaystyle L'}$ ${\displaystyle T_{1}\mid S,\ldots ,T_{m}\mid S}$

Formulaciones

Subárbol de acuerdo homeomórfico máximo [1]

Esta versión requiere que los subárboles sean homeomórficos entre sí. ${\displaystyle T_{1}\mid S,\ldots ,T_{m}\mid 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 están enraizados y que los subárboles contienen 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 sus estrechos vínculos con la filogenia, esta formulación es a menudo lo que se entiende cuando uno se refiere al problema del "subárbol de máxima concordancia". ${\displaystyle T_{1},\ldots ,T_{m}}$ ${\displaystyle T_{1}\mid S,\ldots ,T_{m}\mid S}$

Otras variantes

Existen otras formulaciones, por ejemplo, el subárbol de acuerdo isomórfico máximo (enraizado) ^[1] donde requerimos que los subárboles sean isomórficos entre sí.

Ver también

• Minería frecuente de subárboles

Referencias

1. Amir, A.; Keselman, D. (1 de diciembre de 1997). "Subárbol de máxima concordancia en un conjunto de árboles evolutivos: métricas y algoritmos eficientes". Revista SIAM de Computación . 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 coincidencias bipartitas desequilibradas". Revista de algoritmos . 40 (2): 212–233. arXiv : cs/0101010 . doi :10.1006/jagm.2001.1163.