Estudiamos dos problemas en filogenética computacional. El primero es la compatibilidad de árboles. La entrada es una colección de árboles filogenéticos sobre diferentes conjuntos de especies que se superponen parcialmente. El objetivo es encontrar un solo árbol filogenético que muestre todas las relaciones evolutivas implícitas por . El segundo problema es la filogenia perfecta dirigida incompleta (IDPP). La entrada es una matriz de datos que describe una colección de especies por un conjunto de caracteres, donde falta parte de la información. La pregunta es si existe una manera de completar la información faltante para que la matriz resultante pueda ser explicada por un árbol filogenético que cumpla ciertas condiciones. Explicamos la conexión entre la compatibilidad de árboles y IDPP y mostramos que un algoritmo reciente de compatibilidad de árboles es efectivamente una generalización de un algoritmo IDPP anterior. Ambos algoritmos dependen en gran medida de mantener los componentes conectados de un grafo bajo una secuencia de eliminaciones de aristas y vértices, para lo cual utilizan la estructura de datos de conectividad dinámica de Holm et al., conocida como HDT. Presentamos un estudio computacional de algoritmos para la compatibilidad de árboles y IDPP. Mostramos experimentalmente que sustituir HDT por una estructura de datos mucho más simple, esencialmente una versión de un solo nivel de HDT, mejora el rendimiento de ambos algoritmos en la práctica. Damos justificaciones empíricas y teóricas parciales para esta observación.