Tesis doctoral de Angel Corberan Salvador
El problema del cartero rural (rpp) es un caso general del problema del cartero chino donde se requiere que un subconjunto del conjunto de aristas de un grafo no dirigido dado sea atravesado con el minimo coste. Si este subconjunto no forma un grafo conexo sino un cierto numero de componenetes desconectados entre si el problema es np-completo y es tambien una generalizacion del problema del agente viajero (tsp). En la memoria presentamos el estudio de este problema y presentamos un algoritmo de branch and bround para la solucion exacta del rpp basado en cotas calculadas a partir de la relajacion lagrangiana y en la saturacion de algunos de los nudos del arbol mediante la resolucion de problemas de 1-matching de coste minimo. Se proporcionan resultados computacionales para grafos de hasta 84 vertices 180 aristas 74 aristas requeridas.
Datos académicos de la tesis doctoral «Circuitos eulerianos optimos en grafos no dirigidos: el problema del cartero rural«
- Título de la tesis: Circuitos eulerianos optimos en grafos no dirigidos: el problema del cartero rural
- Autor: Angel Corberan Salvador
- Universidad: Universitat de valéncia (estudi general)
- Fecha de lectura de la tesis: 01/01/1982
Dirección y tribunal
- Director de la tesis
- Marco Antonio López Cerdá
- Tribunal
- Presidente del tribunal: Marco Antonio López Cerdá
- Rafael Romero Villafranca (vocal)
- Segundo Gutierrez Cabria (vocal)
- Pedro Albertos Pérez (vocal)
