18 citations · 100 across the 28 of their papers we have counts for
Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Parameter-Free Triangle Counting
Asaf Etgar, Anna Gilbert, Quanquan Liu +1
Given an undirected, unweighted graph with vertices and edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph count…
cs.DS2026
Scalable Triangle Counting: The Threshold Algorithm
Asaf Etgar, Anna Gilbert, Quanquan C. Liu +1
We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm---read edges from the stream until triangles are observed in the pref…
cs.DS2026
Matchings via Random Greedy Independent Set: A Simpler Algorithm and Analysis
Andrew McGregor
We show that a simple extension of the randomized greedy maximal independent set algorithm yields a constant approximation for the maximum matching problem. The algorithm is a simp…