Circulation problem

A network-flow problem that assigns flow to directed edges while balancing inflow and outflow at every vertex, often subject to lower and upper edge bounds.

Flow conservation: A constraint requiring the total flow entering a vertex to equal the total flow leaving it. It is the defining balance condition at every vertex in a circulation.
Directed graph: A graph whose edges have orientations from one vertex to another. Circulation assigns flow to oriented edges rather than undirected connections.
Bipartite matching: A set of edges in a bipartite graph with no shared endpoints. Matching constraints can be represented using unit-capacity flow and circulation constructions.
Maximum-flow problem: A network-flow problem that maximizes flow from a specified source to a specified sink. Unlike circulation, it permits net flow to enter and leave designated terminals.
Lower-bounded flow: A network flow in which each edge has a required minimum flow as well as a capacity limit. Lower bounds are the distinctive constraints that complicate circulation feasibility.
Network flow: A mathematical model that sends quantities through a directed network subject to edge capacities. Circulation is a network-flow model with conservation imposed everywhere and no designated source or sink.
Transportation problem: An optimization problem that ships goods from suppliers to demand locations while minimizing cost. Supply and demand balance naturally becomes flow conservation with bounds.
Minimum-cost circulation: A circulation satisfying edge bounds that minimizes the sum of flow multiplied by edge cost. It adds an objective to the feasibility problem while preserving vertex balance.
Maximum flow: The problem of sending as much flow as possible from a designated source to a designated sink without exceeding capacities. A circulation with bounds can be tested by transforming it into a maximum-flow instance.
Capacity constraint: A bound limiting the amount of flow that can pass through an edge. Upper edge bounds restrict how much circulation each connection can carry.

Linked from 5 pages