pipette
ENEnglish

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

Aditya Anand, Thatchaphol Saranurak, Benyu Wang

PreprintDice ser un gran avance

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 .

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: SODA 2027