Tesis doctoral de José Ramon Portillo Fernandez
El área de investigación sobre dibujos de grafos constituye una importante conexión entre diversos campos de la matemática, tales como la algoritmica, la geometria computacional y la teoria topológica de grafos. Dentro de ella, el estudio de las inmersiones ortogonales ocupan un lugar importante por su aplicación a diversos problemas: diseño de circuitos vlsi, donde da lugar a diversos problemas de optimización, creación de diagramas de flujo y organigramas, diseño de bases de datos en ingenieria del software y problemas de etiquetado de mapas y otras aplicaciones en sistemas de información geografica. motivados por el trabajo de raghavan et al. Sobre el conocido problema eosp (emparejamiento ortogonal simple en el plano), nos planteamos en primer lugar la extensión de este problema a otras superficies. Este tema constituye la primera parte de la memoria que se presenta. Se estudian en ella la complejidad computacional de los problemas de emparejamiento ortogonal simple (eos), mostrando en primer lugar el comportamiento polinomial del problema cuando únicamente existen dos posibles caminos entre cada pareja de puntos. Sin embargo, el problema con un mayor numero de caminos entre cada pareja de puntos. Sin embargo, el problema con un mayor numero de caminos, asi como el problema general resultan ser np-completos y el problema de optimización asociado a este ultimo es por lo tanto np-duro. otra ampliación necesaria del problema eosp es estudiar, no las conexiones entre parejas, sino entre grupos de puntos usando inmersiones ortogonales de grafos, permitiendo un numero de codos superior a uno por cada inmersión. este estudio, realizado en el pleno ocupa la segunda parte de la memoria. en ella se clasifican los problemas de conexión ortogonal plana según su complejidad computacional. En primer lugar, caracterizamos una serie de problemas resolubles en tiempo polinomial mediante reducción a problemas de logica simbolica o
Datos académicos de la tesis doctoral «Problemas de conexiones ortogonales«
- Título de la tesis: Problemas de conexiones ortogonales
- Autor: José Ramon Portillo Fernandez
- Universidad: Sevilla
- Fecha de lectura de la tesis: 14/02/2002
Dirección y tribunal
- Director de la tesis
- María De Los Angeles Garrido Vizuete
- Tribunal
- Presidente del tribunal: jose Muñoz perez
- pedro Real jurado (vocal)
- ferran Hurtado díaz (vocal)
- Ramos alonso Mª rosario (vocal)