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

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2002
Accession Number
ADA411769

Entities

People

  • Ozgur Erken

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computer Science
  • Computers
  • Flow Network
  • Integer Programming
  • Intelligence Collection
  • Local Area Networks
  • Mesh Networks
  • Military Operations
  • Network Protocols
  • Network Topology
  • Networks
  • Operating Systems
  • Operations Research
  • Theoretical Computer Science
  • Topology

Readers

  • Aerodynamics/Aeronautics.
  • Operations Research
  • Trauma or Military Medicine

Technology Areas

  • Space