Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649188 | Discrete Mathematics | 2009 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
MartÃn Matamala, Eduardo Moreno,