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.
Departamento de Matemática
Pabellón I - Ciudad Universitaria
1428 - Buenos Aires REPÚBLICA ARGENTINA
dummy+54 (11) 5285-7618
dummy secre@dm.uba.ar