Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation
En palabras de los autores
We present a significantly improved -fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph that, given any set of failed edges of size , answers whether is strongly connected. For every constant , our oracle only uses space and query time. No prior result can achieve space and query time, even when . Previous oracles either require query time [BCR18], or space [vdBS19]. Our main technical contribution is a rooted version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph , an integer , and a source vertex , we can sample a set of edges such that each minimal -rooted cut of size at most becomes an -rooted min-cut in with probability .
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: SODA 2027