3 papers
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
Metric repair is two problems: Which edges, and what weights
Asaf Etgar, Anna Gilbert
Real distance data rarely cooperate: measurements are noisy, observations are missing, and the numbers that result seldom satisfy the triangle inequality. A family of methods exist…
cs.DS2026
Structural Tractability Frontiers for Metric Repair
Asaf Etgar, Anna C. Gilbert, Jamie Tucker-Foltz
Given a graph labeled with positive distances on each edge, what is the fewest number of edge distances that must be modified for to become a metric? It is known that this…