A branch-and-bound algorithm for the network diversion problem
Loading...
Authors
Erken, Ozgur
Subjects
Networks
Cuts
Network diversion
Simple path
Enumeration
Branch-and-bound
Cuts
Network diversion
Simple path
Enumeration
Branch-and-bound
Advisors
Wood, R. Kevin
Date of Issue
2002-12
Date
December 2002
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
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 ED . We develop and test a specialized branch-and-bound 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 nonstandard, 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.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
xvi, 37 p. : ill.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner