Branch-and-bound Algorithm for the Network Diversion Problem

摘要

In the network diversion problem (NDP), we must find a minimum-weight set of edges in a directed graph G=(V,E) whose deletion forces all s-t communication to pass through one or more diversion edges in a diversion set E(D). We develop and test a specialized branch-and-hound algorithm for this NP- complete problem. The algorithm is based on partitioning the solution space with respect to edges in certain s-t cuts and yields a non- standard, non-binary enumeration tree. The algorithm is coded in Java version 1.4 and run on a 1.5 MHz Pentium IV computer with 384 megabytes of RAM. An instance of NDP on a grid graph with 2502 vertices, 9900 edges and one diversion edge is solved in 5.66 seconds; the same problem with 10 diversion edges is solved in only 0.84 seconds.