Accession Number:

ADA411769

Title:

A Branch-and-bound Algorithm for the Network Diversion Problem

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

2002-12-01

Pagination or Media Count:

55.0

Abstract:

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.

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE