Resumen

En este encuentro contaré el trabajo realizado por los autores Toshinobu Kashiwabara & Toshio Fujisawa titulado An NP-Complete Problem On Interval Graph publicado en 1979, en el cual demuestran la NP-completitud del problema de aumentación de grafos arbitrarios a grafos de intervalos. Los grafos de intervalos, conocidos por sus aplicaciones en biología, informática y programación de tareas, son aquellos grafos cuyas aristas pueden ser representadas por intervalos en una línea real, donde dos vértices están conectados si y sólo si sus intervalos se solapan.

El artículo presenta una prueba rigurosa de la NP-completitud mediante una reducción desde el problema de Arreglo Lineal Óptimo (OLA), otro problema conocido por ser NP-completo.