Cut feasibility for a rearrangeable triangle
ID: cut-feasibility-for-a-rearrangeable-triangle
The three cyclic versions of this inequality are necessary and sufficient for routing unit calls on a triangle with complete instantaneous rearrangement. Necessity counts endpoint calls through a node cut. For sufficiency, at most one call count can exceed its direct-link capacity, since any two such excesses would violate their common endpoint cut. Route that one excess along the two other links; the two relevant cut inequalities guarantee room there. This gives an exact reduction to a loss network with a virtual resource at each node.
New to topics? Read the docs here!