Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

On Distributed Computation of the Minimum Triangle Edge Transversal
event speaker icon
Majd Khoury (M.Sc. Thesis Seminar)
event date icon
Tuesday, 02.05.2023, 10:30
event location icon
Zoom Lecture: 96304259439 and Taub 601
event speaker icon
Advisor: Prof. Keren Censor-Hillel
In this work, we study the complexity of computing the distance of a graph from being triangle-free in distributed settings, that is, computing the minimum number of edges that must be removed to achieve a graph without triangles. We present lower bounds for the exact solution showing that this task is “as hard as it gets”. We also show fast algorithms for approximate solutions in multiple distributed models.