Portal de Periódicos da CAPES

Problemas de rutas por arcos

1983; Volume: 7; Issue: 3 Linguagem: Espanhol

Enrique Benavent López, Vicente Campos Aucejo, Ángel Corberán Salvador, Enrique Mota Vidal,

Advanced Graph Theory Research

El objetivo de este articulo es ofrecer una vision general de la situacion actual de la investigacion en Problemas de Rutas por Arcos, que consisten, basicamente, en encontrar rutas optimas que atraviesen las aristas o/y arcos de un grafo dado. Se analizan, entre otros, el Problema del Cartero Chino (definido sobre grafos dirigidos, no dirigidos o mixtos), el Problema del Cartero Rural (dirigido y no dirigido), asi como el problema de los m-Carteros con alguna de sus variantes. En todos los casos se ha intentado ofrecer los resultados existentes relativos a: complejidad de los problemas, algoritmos exactos desarrollados, asi como metodos heuristicos con el correspondiente analisis del peor caso