EUVIMEDEUVIMED entdecken
Crossref

Approximately counting independent sets in bipartite graphs via graph containers

Matthew Jenssen, Will Perkins, Aditya Potukuchi

Random Structures & Algorithms · 2023-08 · 63 (1) · 215-241

DOI: 10.1002/rsa.21145 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 15.02.2023. Verfasst von Matthew Jenssen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first algorithm applies to ‐regular, bipartite graphs satisfying a weak expansion condition: when is constant, and the graph is a bipartite ‐expander, we obtain an FPTAS for the number of independent sets. Previously such a result for was known only for graphs satisfying the much stronger expansion conditions of random bipartite graphs. The algorithm also applies to weighted independent sets: for a ‐regular, bipartite ‐expander, with fixed, we give an FPTAS for the hard‐core model partition function at fugacity . Finally we present an algorithm that applies to all ‐regular, bipartite graphs, runs in time , and outputs a ‐approximation to the number of independent sets.

Förderung

  • National Science Foundation

Zitieren

APA

Jenssen, M., Perkins, W., & Potukuchi, A. (2023). Approximately counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms, 63(1), 215-241. https://doi.org/10.1002/rsa.21145

Vancouver

Jenssen M, Perkins W, Potukuchi A. Approximately counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms. 2023;63(1):215-241. doi:10.1002/rsa.21145

BibTeX
@article{Jenssen2023,
  author = {Jenssen, Matthew and Perkins, Will and Potukuchi, Aditya},
  title = {Approximately counting independent sets in bipartite graphs via graph containers},
  journal = {Random Structures & Algorithms},
  year = {2023},
  volume = {63},
  number = {1},
  pages = {215--241},
  doi = {10.1002/rsa.21145}
}
Kostenlos starten →