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
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
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.
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.