logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro