Name
Abstract | ||
|---|---|---|
We resolve a conjecture proposed by D.E. Knuth concerning a recurrence arising in the satisfiability problem. Knuth's recurrence resembles recurrences arising in the analysis of tries, in particular PATRICIA tries, and asymmetric leader election. We solve Knuth's recurrence exactly and asymptotically, using analytic techniques such as the Mellin transform and analytic depoissonization. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1017/S0963548314000133 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Mellin transform,Leader election,Discrete mathematics,Combinatorics,Knuth's Algorithm X,Boolean satisfiability problem,Satisfiability,Conjecture,Mathematics | Journal | 23 |
Issue | ISSN | Citations |
SP5 | 0963-5483 | 1 |
PageRank | References | Authors |
0.37 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippe Jacquet | 1 | 714 | 90.11 |
| Charles Knessl | 2 | 215 | 40.43 |
| Wojciech Szpankowski | 3 | 1557 | 192.33 |