logo móvil
Contáctanos

Algoritmos eficientes para listar subgrafos

Autores: Zechner, Niklas; Lingas, Andrzej

Idioma: Inglés

Editor: MDPI

Año: 2014

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro