Caminos de Santiago: small separating path systems for complete graphs.

Summary: In a communication network of n nodes, each linked to every other, a single link fails. How can we discover which link is broken without going through the burdensome process of examining separately all \(\Theta(n^2)\) of them? A quick way to determine the faulty link would be to propagate messages through a designated set of paths S, such that for every two links there exists a path in S that contains exactly one of them. We say that such a set S (weakly) separates the network. It is known that a separating path system for a network of n nodes must contain at least n-1 paths. Recently, Fernandes, Oliveira Mota and Sanhueza-Matamala proved that (1+o(1))n paths suffice.

Posted on Mar 7, 2024 in Seminars, SIPo (Seminario de Investigadores Postdoctorales)