Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 23 de abril de 2024
  

Tour eulerià sense girs en U en un graf orientat simple.

Título original Tour eulerià sense girs en U en un graf orientat simple.
Título inglés Eulerian tour without U-turns in a simple digraph.
Título español Recorrido euleriano sin giros en U en un grafo orientado simple.
Autor/es Soler Fernández, David
Organización Dep. Mat. Apl. Univ. Politéc. Valencia, Valencia, España
Revista 0210-8054
Publicación 1998, 22 (3): 471-489, 11 Ref.
Tipo de documento articulo
Idioma Catalán
Resumen español Siendo G = (V,A) un grafo orientado euleriano simple, se estudia aquí la búsqueda de un recorrido euleriano sin giros en U, es decir, sin recorrer consecutivamente pares de arcos (u,v), (v,u), u,v Î V. Desconocida la complejidad de este problema, se generaliza un resultado de un caso particular resuelto en tiempo polinomial, proporcionando una condición bajo la cual se puede construir en tiempo polinomial un recorrido euleriano sin giros en U sobre G. Esta condición se basa, además, en la eliminación de vértices candidatos a contener giros en U en un recorrido euleriano con el mínimo número de ellos.
Clasificación UNESCO 120704
Palabras clave español Circuitos eulerianos ; Teoría de grafos ; Problema general de rutas ; Algoritmos polinomiales
Código MathReviews MR1672936
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es