Accession Number : ADA267488


Title :   Full and Partial Multicommodity Cuts


Descriptive Note : Doctoral thesis,


Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH


Personal Author(s) : Burk, Roger C


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267488.pdf


Report Date : Jan 1993


Pagination or Media Count : 165


Abstract : The problems of finding multicommodity cuts and partial multicommodity cuts in graphs are investigated. A multicommodity flow graph is a graph with k vertex pairs identified as the terminals (source and sink) for k commodities. A (full) multicommodity cut is a set of elements (edges or vertices) whose removal from such a graph cuts all source-to-sink paths for all commodities. A partial multicommodity cut is defined as a set of elements whose removal prevents more than a given number r of commodities from being connected by disjoint paths. For the full multicommodity cut problem, polynomial algorithms are found for any fixed k in a T-planar graph (one with all terminals on the boundary) and for k = 3 in a general planar graph. The T-planar problem is shown to be NP-complete for varying k unless the terminals are in non- crossing order; a polynomial algorithm is developed for that case. For partial multicommodity cuts, polynomial algorithms are developed for r = k - 1, r = k and r = 1 in T-planar non-crossing graphs. In the special case in which there is a common source for every commodity, the partial multicommodity cut problem is shown to be polynomial as long as r or k - r is bounded, even in general graphs.


Descriptors :   *GRAPHS , *COMMODITIES , ALGORITHMS , REMOVAL , BOUNDARIES , FLOW , TERMINALS , CROSSINGS , POLYNOMIALS , PROBLEM SOLVING , EDGES


Subject Categories : Numerical Mathematics
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE