Algoritmos eficientes para listar subgrafos
Autores: Zechner, Niklas; Lingas, Andrzej
Idioma: Inglés
Editor: MDPI
Año: 2014
Acceso abierto
Artículo científico
2014
Algoritmos eficientes para listar subgrafos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Subgrafo
Isomorfismo
Algoritmo
Listado
Triángulos
Inducido
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
El isomorfismo de subgrafos es un problema fundamental en la teoría de grafos. En este artículo nos enfocamos en listar subgrafos isomorfos a un grafo de patrón dado. Primero, examinamos el algoritmo de Chiba y Nishizeki para listar subgrafos completos de tamaño fijo, y mostramos que no se puede extender a subgrafos generales de tamaño fijo. Luego, consideramos el algoritmo de Gsieniec para encontrar múltiples testigos de un producto de matrices booleanas, y lo utilizamos para diseñar un nuevo algoritmo sensible a la salida para listar todos los triángulos en un grafo. Como corolario, obtenemos un algoritmo sensible a la salida para listar subgrafos e subgrafos inducidos isomorfos a un patrón fijo arbitrario.
Descripción
El isomorfismo de subgrafos es un problema fundamental en la teoría de grafos. En este artículo nos enfocamos en listar subgrafos isomorfos a un grafo de patrón dado. Primero, examinamos el algoritmo de Chiba y Nishizeki para listar subgrafos completos de tamaño fijo, y mostramos que no se puede extender a subgrafos generales de tamaño fijo. Luego, consideramos el algoritmo de Gsieniec para encontrar múltiples testigos de un producto de matrices booleanas, y lo utilizamos para diseñar un nuevo algoritmo sensible a la salida para listar todos los triángulos en un grafo. Como corolario, obtenemos un algoritmo sensible a la salida para listar subgrafos e subgrafos inducidos isomorfos a un patrón fijo arbitrario.