Consideremos un grafo que pertenece a una clase de grafos. Estamos interesados en conectar un nodo a por un solo borde donde ; llamamos a dicho borde una cola. Dado que el grafo resultante de después de la adición de la cola, denotado , no necesariamente pertenece a la clase , queremos calcular el número de no-bordes de en una -completación mínima de , es decir, el número mínimo de no-bordes (excluyendo la cola) que se deben agregar para que el grafo resultante pertenezca a . En este documento, estudiamos este problema para las clases de grafos divididos, cuasi-umbral, umbral y -disperso y presentamos algoritmos de tiempo lineal explotando la estructura de los grafos divididos y la representación de árbol de los grafos cuasi-umbral, umbral y -disperso.