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

DOI10.1002/rsa.20994zbMath1522.68746arXiv2005.00064OpenAlexW3121951219MaRDI QIDQ6074650

Jacques Verstraete, Jiaxi Nie

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.00064

zbMATH Keywords

independent setsrandomized greedy algorithmhypergraphs with large girth

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items (1)

The matching process and independent process in random regular graphs and hypergraphs

Cites Work

• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• Extremal uncrowded hypergraphs
• A note on the independence number of triangle-free graphs. II
• Large independent sets in regular graphs of large girth
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• Improved lower bounds on k‐independence
• On uncrowded hypergraphs
• New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth