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.
Original language | English |
---|---|
Pages (from-to) | 5298-5304 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 309 |
Issue number | 17 |
DOIs | |
State | Published - 6 Sep 2009 |
Keywords
- De Bruijn sequences
- Eulerian circuits
- Labelled digraph