Package com.jgalgo.alg.flow

Class MaximumFlowDinicDynamicTrees

java.lang.Object
com.jgalgo.alg.connect.MinimumEdgeCutStAbstract
com.jgalgo.alg.flow.MaximumFlowAbstract
com.jgalgo.alg.flow.MaximumFlowAbstractWithResidualNet
com.jgalgo.alg.flow.MaximumFlowDinicDynamicTrees
All Implemented Interfaces:
MinimumEdgeCutSt, MaximumFlow
public class MaximumFlowDinicDynamicTrees extends MaximumFlowAbstractWithResidualNet
Dinic's algorithm for maximum flow using dynamic trees.

Using dynamic trees, the algorithm of Dinic to maximum flow problem is implemented in time \(O(m n \log n)\) and linear space. In practice, the (relative) complicated implementation of dynamic trees have little gain in the overall performance, and its probably better to use some variant of the MaximumFlowPushRelabel, which has worse theoretically bounds, but runs faster in practice.

Author:
Barak Ugav
See Also:

  • Constructor Details

    • MaximumFlowDinicDynamicTrees

      public MaximumFlowDinicDynamicTrees()
      Create a new maximum flow algorithm object.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.