Minimal Eulerian circuit in a labeled digraph

Eduardo Moreno, Martín Matamala

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

4 Citas (Scopus)

Resumen

Let G = (V, A) be an Eulerian directed graph with an arolabelingr - In this work we study the problem of finding an Eulerian circuit of lexicographically minimal label among all Eulerian circuits of the graph. We prove that this problem is NP-hard by showing a reduction from the DIRECTED-HAMILTONIAN-CIRCUIT problem. If the labeling of the arcs is such that arcs going out from the same vertex have different labels, the problem can be solved in polynomial time. We present an algorithm to construct the unique Eulerian circuit of lexicographically minimal label starting at a fixed vertex. Our algorithm is a recursive greedy algorithm which runs in O(|A|] steps. We also show an application of this algorithm to construct the minimal De Bruijn sequence of a language.

Idioma originalInglés
Título de la publicación alojadaLATIN 2006
Subtítulo de la publicación alojadaTheoretical Informatics - 7th Latin American Symposium, Proceedings
Páginas737-744
Número de páginas8
DOI
EstadoPublicada - 2006
EventoLATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile
Duración: 20 mar. 200624 mar. 2006

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen3887 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

ConferenciaLATIN 2006: Theoretical Informatics - 7th Latin American Symposium
País/TerritorioChile
CiudadValdivia
Período20/03/0624/03/06

Huella

Profundice en los temas de investigación de 'Minimal Eulerian circuit in a labeled digraph'. En conjunto forman una huella única.

Citar esto