Name
Abstract | ||
|---|---|---|
Consider two people, P and Q, connected with a bidirectional communication link. Let P have a binary string 2 and let Q have y, The string y can be obtained from x by a small number k of editing operations: inserting/deleting a bit and copying/moving/deleting a block (substring). Our problem is to communicate the string y to P using a small number of bits in both directions. We present a probabilistic algorithm for that task aud prove that for any Z, y and E > 0 the algorithm communicates y (the string that Q has) to P with probability 1 - E using poly(log 1~1, log )y), loge-l, k) bits. The running time is poly()z), )y),log~-l). |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1145/314613.314720 | Theor. Comput. Sci. |
Keywords | Field | DocType |
communication link,probabilistic algorithm | Communication link,Discrete mathematics,Randomized algorithm,Divergence-from-randomness model,Combinatorics,Substring,Estimation of distribution algorithm,Computer science,Probabilistic CTL,Probabilistic analysis of algorithms,Bidirectional communication | Journal |
Volume | Issue | ISBN |
233 | 1-2 | 0-89871-410-9 |
Citations | PageRank | References |
4 | 0.50 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre V. Evfimievski | 1 | 501 | 41.76 |