Show simple item record

dc.contributor.advisorWood, R. Kevin
dc.contributor.authorErken, Ozgur
dc.dateDecember 2002
dc.date.accessioned2012-03-14T17:40:08Z
dc.date.available2012-03-14T17:40:08Z
dc.date.issued2002-12
dc.identifier.urihttp://hdl.handle.net/10945/4025
dc.descriptionApproved for public release, distribution is unlimiteden_US
dc.description.abstractIn 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.en_US
dc.description.urihttp://archive.org/details/abranchandboundl109454025
dc.format.extentxvi, 37 p. : ill.en_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsCopyright is reserved by the copyright owneren_US
dc.subject.lcshComputer networksen_US
dc.subject.lcshBranch and bound algorithmsen_US
dc.titleA branch-and-bound algorithm for the network diversion problemen_US
dc.typeThesisen_US
dc.contributor.secondreaderCarlyle, Matthew
dc.contributor.departmentOperations Research (OR)
dc.subject.authorNetworksen_US
dc.subject.authorCutsen_US
dc.subject.authorNetwork diversionen_US
dc.subject.authorSimple pathen_US
dc.subject.authorEnumerationen_US
dc.subject.authorBranch-and-bounden_US
dc.description.serviceLieutenant Junior Grade, Turkish Navyen_US
etd.thesisdegree.nameM.S. in Operations Researchen_US
etd.thesisdegree.levelMastersen_US
etd.thesisdegree.disciplineOperations Researchen_US
etd.thesisdegree.grantorNaval Postgraduate Schoolen_US
etd.verifiednoen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record