Aproximando el mínimo recorrido de cobertura de un digrafo
Autores: Nguyen, Viet Hung
Idioma: Inglés
Editor: Molecular Diversity Preservation International (MDPI)
Año: 2011
Acceso abierto
Artículo científico
2011
Aproximando el mínimo recorrido de cobertura de un digrafo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Grafo dirigido
Costo no negativo
Recorrido dirigido que cubre
Ciclo
Costo mínimo
Algoritmos de aproximación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 39
Citaciones: Sin citaciones
Dado un grafo dirigido con costos no negativos en los arcos, una cobertura de recorrido dirigido es un ciclo (no necesariamente simple) en el cual la cabeza o la cola (o ambas) de cada arco en son tocadas por . El problema de la cobertura de recorrido dirigido de costo mínimo (DToCP), que consiste en encontrar una cobertura de recorrido dirigido de costo mínimo, es -difícil. Por lo tanto, resulta interesante diseñar algoritmos de aproximación con garantía de rendimiento para resolver este problema. Aunque su contraparte no dirigida (ToCP) ha sido estudiada en años recientes, hasta donde sabemos, el DToCP sigue siendo ampliamente abierto. En este documento, presentamos un algoritmo de aproximación de 2 log()-para el DToCP.
Descripción
Dado un grafo dirigido con costos no negativos en los arcos, una cobertura de recorrido dirigido es un ciclo (no necesariamente simple) en el cual la cabeza o la cola (o ambas) de cada arco en son tocadas por . El problema de la cobertura de recorrido dirigido de costo mínimo (DToCP), que consiste en encontrar una cobertura de recorrido dirigido de costo mínimo, es -difícil. Por lo tanto, resulta interesante diseñar algoritmos de aproximación con garantía de rendimiento para resolver este problema. Aunque su contraparte no dirigida (ToCP) ha sido estudiada en años recientes, hasta donde sabemos, el DToCP sigue siendo ampliamente abierto. En este documento, presentamos un algoritmo de aproximación de 2 log()-para el DToCP.