Gráficos de extremidades definidos por algoritmos de búsqueda
Autores: Berry, Anne; Blair, Jean R.S.; Bordat, Jean-Paul; Simonet, Geneviève
Idioma: Inglés
Editor: Molecular Diversity Preservation International
Año: 2010
Acceso abierto
Artículo científico
2010
Gráficos de extremidades definidos por algoritmos de búsqueda
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmos de búsqueda de grafos
Extremos
Grafo cordal
MLS
MLSM
Separadores mínimos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
Los algoritmos de búsqueda en grafos han explotado las extremidades de los grafos, como las hojas de un árbol y los vértices simpliciales de un grafo cordal. Recientemente, varios algoritmos de búsqueda en grafos conocidos se han expresado colectivamente como dos algoritmos genéricos llamados MLS y MLSM. En este documento, investigamos las propiedades del vértice que es numerado como 1 por MLS en un grafo cordal y por MLSM en un grafo arbitrario. Explicamos cómo este vértice es una extremidad del grafo. Además, mostramos la propiedad notable de que los separadores mínimos incluidos en el vecindario de este vértice están totalmente ordenados por inclusión.
Descripción
Los algoritmos de búsqueda en grafos han explotado las extremidades de los grafos, como las hojas de un árbol y los vértices simpliciales de un grafo cordal. Recientemente, varios algoritmos de búsqueda en grafos conocidos se han expresado colectivamente como dos algoritmos genéricos llamados MLS y MLSM. En este documento, investigamos las propiedades del vértice que es numerado como 1 por MLS en un grafo cordal y por MLSM en un grafo arbitrario. Explicamos cómo este vértice es una extremidad del grafo. Además, mostramos la propiedad notable de que los separadores mínimos incluidos en el vecindario de este vértice están totalmente ordenados por inclusión.