A Branch-and-bound Algorithm for the Network Diversion Problem
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
In the network diversion problem NDP, we must find a minimum-weight set of edges in a directed graph GV,E whose deletion forces all s-t communication to pass through one or more diversion edges in a diversion set ED. 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.
- Numerical Mathematics
- Computer Programming and Software