Full and Partial Multicommodity Cuts
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1993
- Accession Number
- ADA267488
Entities
People
- Roger C. Burk
Organizations
- Air Force Institute of Technology