Noticias en español
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....
Read More