6 papers
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…
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…
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…
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…
On the Connectivity and Diameter of Geodetic Graphs
Asaf Etgar, Nati Linial
A graph is geodetic if between any two vertices there exists a unique shortest path. In 1962 Ore raised the challenge to characterize geodetic graphs, but despite many attempts…
The -Rank and Size of Graphs
Gal Beniamini, Asaf Etgar, Yael Kirkpatrick
We consider the extremal family of graphs of order in which no two vertices have identical neighbourhoods, yet the adjacency matrix has rank only over the field of two el…