Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2007.11.027 | Discrete Mathematics |
Keywords | Field | DocType |
vertex,linear time,de bruijn sequence,etiquette,directed graph,digraph,de bruijn graph,label,np complete problem | Discrete mathematics,Combinatorics,BEST theorem,Vertex (geometry),Directed graph,Eulerian path,De Bruijn graph,De Bruijn sequence,Time complexity,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
309 | 17 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.45 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martín Matamala | 1 | 158 | 21.63 |
| Eduardo Moreno | 2 | 115 | 14.44 |