logo móvil
Contáctanos

Recientes avances en la búsqueda de gráficos impulsada por instancias positivas

Autores: Bannach, Max; Berndt, Sebastian

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

Acceso abierto

Artículo científico
2022

Recientes avances en la búsqueda de gráficos impulsada por instancias positivas


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Investigación
Gráfico
Algoritmo
Programación dinámica
Subinstancias
Parámetro

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
La investigación sobre la similitud de un grafo con un árbol, llamado el de grafo, ha experimentado un enorme aumento en la última década, pero un algoritmo prácticamente rápido para esta tarea fue descubierto recientemente por Tamaki (ESA 2017). Se basa en la programación dinámica y aprovecha el hecho de que el número de subinstancias positivas suele ser sustancialmente menor que el número de todas las subinstancias. Los algoritmos que producen solo tales subinstancias se llaman (PID). El parámetro tiene una historia similar. Fue popularizado a través del proyecto de esparcidad del grafo y se entiende bien teóricamente, pero el primer algoritmo práctico fue descubierto recientemente por Trimble (IPEC 2020) y se basa en el mismo paradigma. Presentamos una vista alternativa y unificadora de tales algoritmos desde la perspectiva de los grafos de configuración correspondientes en ciertos juegos de dos jugadores. Esto resulta en un único algoritmo que puede calcular una amplia gama de parámetros de grafo importantes como el ancho de árbol, el ancho de camino y la profundidad de árbol. Complementamos este algoritmo con una nueva estructura de datos aleatorizada que acelera la enumeración de subproblemas en algoritmos conducidos por instancias positivas.

Otros recursos que podrían interesarte

Temas Virtualpro