Efficient Computing of Disaster-Disjoint Paths: Greedy and Beyond

Vass, Balázs and Bérczi-Kovács, Erika and Gyimesi, Péter and Tapolcai, János (2024) Efficient Computing of Disaster-Disjoint Paths: Greedy and Beyond. In: IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS).

Preview

Text SRLG_disj__routing__greedy___INFOCOM_24_poster_abstract.pdf Download (134kB) | Preview

Abstract

In a network topology G , we say a set of st-paths are disaster-disjoint if no disaster strikes more than one path. In this poster, we explore the basic capabilities and limitations of greedy and more advanced algorithms for computing maximal collections of such paths in planar networks. An algorithm is greedy if it generates consecutive paths P1,P2,… according to a simple rule. In the simplest setting, the only rule is that Pi+1 is the closest clockwise disaster-disjoint from Pi . We find that the simplest greedy may fail even when 1) G is planar, 2) each disaster region is connected, and 3) each node failure (apart from s and t ) is considered possible. Adding a simple rule explained in [1] yields a correct polynomial-time algorithm for the above problem. Finally, we digest a recent related near-linear runtime algorithm of [2] solving a more general problem and discuss the underlying relations among the foundations of these algorithms.

Actions (login required)

Edit Item