EUVIMEDEUVIMED entdecken
Crossref

Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

Jiaxi Nie, Jacques Verstraëte

Random Structures & Algorithms · 2021-08 · 59 (1) · 79-95

DOI: 10.1002/rsa.20994 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 19.01.2021. Verfasst von Jiaxi Nie und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 16 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we consider a randomized greedy algorithm for independent sets in r ‐uniform d ‐regular hypergraphs G on n vertices with girth g . By analyzing the expected size of the independent sets generated by this algorithm, we show that , where converges to 0 as g → ∞ for fixed d and r , and f ( d , r ) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

Förderung

  • National Science Foundation

Zitieren

APA

Nie, J., & Verstraëte, J. (2021). Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth. Random Structures & Algorithms, 59(1), 79-95. https://doi.org/10.1002/rsa.20994

Vancouver

Nie J, Verstraëte J. Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth. Random Structures & Algorithms. 2021;59(1):79-95. doi:10.1002/rsa.20994

BibTeX
@article{Nie2021,
  author = {Nie, Jiaxi and Verstraëte, Jacques},
  title = {Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth},
  journal = {Random Structures & Algorithms},
  year = {2021},
  volume = {59},
  number = {1},
  pages = {79--95},
  doi = {10.1002/rsa.20994}
}
Kostenlos starten →