4 papers · 1 filter
Witness-Sensitive Detection of Induced Diamonds
Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams +1
We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a minus an edge) in an -vertex graph containing induced diamonds. Our algorithm…
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate -clique counts faster
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
Dell, Lapinskas and Meeks [DLM SICOMP 2022] presented a general reduction from approximate counting to decision for a class of fine-grained problems that can be viewed as hyperedge…
Fast Approximate Counting of Cycles
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, TÄtek [ICALP'22] gave an algorithm that returns a $(…
Faster Cycle Detection in the Congested Clique
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We provide a fast distributed algorithm for detecting -cycles in the \textsf{Congested Clique} model, whose running time decreases as the number of -cycles in the graph incre…