Minimum Eulerian circuits and minimum de Bruijn sequences

Martín Matamala, Eduardo Moreno

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish
Pages (from-to)5298-5304
Number of pages7
JournalDiscrete Mathematics
Volume309
Issue number17
DOIs
StatePublished - 6 Sep 2009

Keywords

  • De Bruijn sequences
  • Eulerian circuits
  • Labelled digraph

Fingerprint

Dive into the research topics of 'Minimum Eulerian circuits and minimum de Bruijn sequences'. Together they form a unique fingerprint.

Cite this