Name
Abstract | ||
|---|---|---|
A simple meta-algorithm is provided to efficiently generate a wide variety of combinatorial objects that can be represented by binary strings with a fixed number of 1s. Such objects include: k-ary Dyck words, connected unit interval graphs, binary strings lexicographically larger than omega, those avoiding 10(k) for fixed k, reversible strings and feasible solutions to knapsack problems. Each object requires only a very simple object-specific subroutine (oracle) that plugs into the generic cool-lex framework introduced by Williams. The result is that each object can be generated in amortized O(1)-time. Moreover, the strings can be listed in either a conventional co-lexicographic order, or in the cool-lex Gray code order. |
Year | Venue | Keywords |
|---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | Bubble language,Gray code,cool-lex,unit interval graph,knapsack,reversible strings,CAT algorithm,necklace,Lyndon word |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Subroutine,Binary strings,Oracle,Gray code,Lexicographical order,Knapsack problem,Mathematics,Bubble,Binary number | Journal | 19.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 6 |
PageRank | References | Authors |
0.51 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Sawada | 1 | 66 | 9.11 |
| Aaron Williams | 2 | 139 | 20.42 |