ABSTRACT
Finding a set of disjoint paths is one of the basic problems in graph theory. This problem appears in many settings in different areas such as communication networks, circuit design, transportation, and many others. Disjoint paths can be used to increase throughput, mitigate failures of network elements, and minimize congestion. Network operators can use disjoint paths to improve resilience to failures, spread the traffic evenly across the network, and maximize the rate of data transfer. For example, to minimize packet loss during an edge failure event, a copy of each packet can be sent along two disjoint paths, which allows the receiver to recover at least one copy of the packet if the failure occurs [2].
