EUVIMEDEUVIMED entdecken
Crossref

Fast and Perfect Sampling of Subgraphs and Polymer Systems

Antonio Blanca, Sarah Cannon, Will Perkins

ACM Transactions on Algorithms · 31.01.2024 · 20 (1) · 1-30

DOI: 10.1145/3632294 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 22.01.2024. Verfasst von Antonio Blanca und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets ) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

Förderung

  • NSF

Zitieren

APA

Blanca, A., Cannon, S., & Perkins, W. (2024). Fast and Perfect Sampling of Subgraphs and Polymer Systems. ACM Transactions on Algorithms, 20(1), 1-30. https://doi.org/10.1145/3632294

Vancouver

Blanca A, Cannon S, Perkins W. Fast and Perfect Sampling of Subgraphs and Polymer Systems. ACM Transactions on Algorithms. 2024;20(1):1-30. doi:10.1145/3632294

BibTeX
@article{Blanca2024,
  author = {Blanca, Antonio and Cannon, Sarah and Perkins, Will},
  title = {Fast and Perfect Sampling of Subgraphs and Polymer Systems},
  journal = {ACM Transactions on Algorithms},
  year = {2024},
  volume = {20},
  number = {1},
  pages = {1--30},
  doi = {10.1145/3632294}
}
Kostenlos starten →