Loading...
Please wait, while we are loading the content...
Similar Documents
Testable algorithms for self-avoiding walks (1994).
| Content Provider | CiteSeerX |
|---|---|
| Author | Randall, Dana Sinclair, Alistair |
| Abstract | We present a polynomial time Monte Carlo algorithm for almost uniformly generating and approximately counting self-avoiding walks in rectangular lattices Z d . These are classical problems that arise, for example, in the study of long polymer chains. While there are a number of Monte Carlo algorithms used to solve these problems in practice, these are heuristic and their correctness relies on unproven conjectures. In contrast, our algorithm depends on a single, widely-believed conjecture that is weaker than preceding assumptions, and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counter-example to the conjecture. 1 Summary 1.1 Background A self-avoiding walk in a graph is a walk which starts at a fixed origin and passes through each vertex at most once. This paper is concerned with self-avoiding walks in lattices, in par... |
| File Format | |
| Publisher Date | 1994-01-01 |
| Access Restriction | Open |
| Subject Keyword | Self-avoiding Walk Testable Algorithm Correctness Relies Uniformly Generating Widely-believed Conjecture Unproven Conjecture Long Polymer Chain Fixed Origin Rectangular Lattice High Probability Classical Problem Monte Carlo Algorithm Polynomial Time Monte Carlo Algorithm |
| Content Type | Text |
| Resource Type | Article |
