Minimum Eulerian circuits and minimum de Bruijn sequences

Matamala M.; Moreno E.

Abstract

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label. © 2007 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Minimum Eulerian circuits and minimum de Bruijn sequences
Título según SCOPUS: Minimum Eulerian circuits and minimum de Bruijn sequences
Título de la Revista: DISCRETE MATHEMATICS
Volumen: 309
Número: 17
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2009
Página de inicio: 5298
Página final: 5304
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0012365X07009399
DOI:

10.1016/j.disc.2007.11.027

Notas: ISI, SCOPUS