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
Acceso al artículo completo