Sesión Matemática DiscretaOrientación óptima de hipergrafos
Gabriel Valiente
Universidad Politécnica de Cataluña, España - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Presentamos el problema de asignar una dirección a las aristas de un hipergrafo de modo que se minimice el número de vértices fuente y sumidero. Consideramos hipergrafos cuyas aristas están divididas en dos subconjuntos disjuntos de vértices, que se convertirán en la cola y la cabeza de la arista al orientarse. Demostramos que el problema es NP-difícil incluso cuando se restringe a hipergrafos donde cada vértice pertenece exactamente a dos aristas, pero que se puede resolver en tiempo polinómico en grafos.
También presentamos una forma más general del problema de orientación de hipergrafos, en la que algunos vértices están restringidos a ser fuente, sumidero o vértice interno. Demostramos que sigue siendo resoluble en tiempo polinomial en grafos mediante un algoritmo de tiempo lineal.
Estos problemas tienen aplicación práctica en la orientación de las reacciones bioquímicas en las redes metabólicas.
Trabajo en conjunto con: Alberto José Ferrari (Universidad Nacional de Rosario, Argentina), Valeria Leoni (Universidad Nacional de Rosario, Argentina) y Graciela Nasini (Universidad Nacional de Rosario, Argentina).