Name
Abstract | ||
|---|---|---|
Given a set H of binary vectors of length n, is there a cyclic listing of H so that every two successive vectors differ in a single coordinate? The problem of the existence of such a listing, which is called a cyclic Gray code of H, is known to be NP-complete in general. The goal of this paper is therefore to specify boundaries between its intractability and polynomial decidability. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2011.09.034 | Discrete Mathematics |
Keywords | Field | DocType |
Gray code,Faulty vertex,Hypercube,Hamiltonian path,Hamiltonian cycle,NP-hard,Polynomial algorithm | Discrete mathematics,Combinatorics,Vertex (geometry),Polynomial,Hamiltonian path,Gray code,Decidability,Time complexity,Mathematics,Hypercube,Bounded function | Journal |
Volume | Issue | ISSN |
312 | 17 | 0012-365X |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomás Dvorák | 1 | 68 | 6.41 |
| Jiří Fink | 2 | 82 | 9.00 |
| Petr Gregor | 3 | 178 | 19.79 |
| Václav Koubek | 4 | 431 | 93.44 |