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.
@article{urn:eudml:doc:40259,
title = {Tour euleri\`a sense girs en U en un graf orientat simple.},
journal = {Q\"uestii\'o},
volume = {22},
year = {1998},
pages = {471-489},
mrnumber = {MR1672936},
language = {ca},
url = {http://dml.mathdoc.fr/item/urn:eudml:doc:40259}
}
Soler Fernández, David. Tour eulerià sense girs en U en un graf orientat simple.. Qüestiió, Tome 22 (1998) pp. 471-489. http://gdmltest.u-ga.fr/item/urn:eudml:doc:40259/