| Autor: |
Shobhna Singh, Jerome Lloyd, Felix Flicker |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Physical Review X, Vol 14, Iss 3, p 031005 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2160-3308 |
| DOI: |
10.1103/PhysRevX.14.031005 |
| Popis: |
We provide a simple algorithm for constructing Hamiltonian graph cycles (visiting every vertex exactly once) on a set of arbitrarily large finite subgraphs of aperiodic two-dimensional Ammann-Beenker (AB) tilings. Using this result, and the discrete scale symmetry of AB tilings, we find exact solutions to a range of other problems which lie in the complexity class NP-complete for general graphs. These include the equal-weight traveling salesperson problem, providing, for example, the most efficient route a scanning tunneling microscope tip could take to image the atoms of physical quasicrystals with AB symmetries; the longest path problem, whose solution demonstrates that collections of flexible molecules of any length can adsorb onto AB quasicrystal surfaces at density one, with possible applications to catalysis; and the three-coloring problem, giving ground states for the q-state Potts model (q≥3) of magnetic interactions defined on the planar dual to AB, which may provide useful models for protein folding. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
