A branch-and-bound algorithm for the network diversion problem
Wood, R. Kevin
MetadataShow full item record
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.
Approved for public release, distribution is unlimited
Showing items related by title, author, creator and subject.
Do patients hospitalised in high-minority hospitals experience more diversion and poorer outcomes? A retrospective multivariate analysis of Medicare patients in California Shen, Yu-Chu; Hsia, Renee Y (2016);Objective: We investigated the association between crowding as measured by ambulance diversion and differences in access, treatment and outcomes between black and white patients. Design: Retrospective analysis. Setting: ...
Tan Soon; Meng Alvin (Monterey, California. Naval Postgraduate School, 2007-06);Pressure on emergency medical services (EMS) is rising. The growth in EMS utilization has coincided with a decline in the number of emergency departments (ED). Between 1994 and 2004, the annual number of ED visits in the ...
New motion planning and real-time localization methods using proximity for autonomous mobile robots Wahdan, Mahmoud A. (Monterey, California. Naval Postgraduate School, 1996-09);One of the most difficult theoretical problems in robotics--motion planning for rigid body robots-- must be solved before a robot can perform real- world tasks such as mine searching and processing. This dissertation ...