Name
Abstract | ||
|---|---|---|
Let G = (V,A) be an Eulerian directed graph with an arc-labeling. In this work we study the problem of finding an Eulerian circuit of lexicographically minimal label among all Eulerian circuits of the graph. We prove that this problem is NP-hard by showing a reduction from the Directed-Hamiltonian-Circuit problem. If the labeling of the arcs is such that arcs going out from the same vertex have different labels, the problem can be solved in polynomial time. We present an algorithm to construct the unique Eulerian circuit of lexicographically minimal label starting at a fixed vertex. Our algorithm is a recursive greedy algorithm which runs in ${\mathcal O}$(|A|) steps. We also show an application of this algorithm to construct the minimal De Bruijn sequence of a language. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11682462_67 | LATIN |
Keywords | Field | DocType |
lexicographically minimal label,eulerian circuit,minimal eulerian circuit,fixed vertex,polynomial time,minimal de bruijn sequence,mathcal o,recursive greedy algorithm,unique eulerian circuit,different label,directed-hamiltonian-circuit problem,de bruijn sequence,eulerian graph,directed graph | Discrete mathematics,Combinatorics,Hamiltonian path,Route inspection problem,Directed graph,Greedy algorithm,Eulerian path,Eulerian number,De Bruijn sequence,Time complexity,Mathematics | Conference |
Volume | ISSN | ISBN |
3887 | 0302-9743 | 3-540-32755-X |
Citations | PageRank | References |
2 | 0.44 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Moreno | 1 | 115 | 14.44 |
| Martín Matamala | 2 | 158 | 21.63 |