Changeset - r879:25804ef35064
« 878:4b1b37
880:0643a9 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Add citations to the scaling MCF algorithms (#180, #184) and improve the doc of their group.
0 3 0
default
3 files changed with 12 insertions and 11 deletions:
doc/groups.dox
6
8
lemon/capacity_scaling.h
2
1
lemon/cost_scaling.h
4
2
↑ Collapse diff ↑
doc/groups.dox
Show white space 6 line context
... ... 
@@ -406,15 +406,13 @@
406 406 
LEMON contains several algorithms for this problem.
407 407 
 - \ref NetworkSimplex Primal Network Simplex algorithm with various
408 408 
   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
409 
 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
410 
   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
409 
 - \ref CostScaling Cost Scaling algorithm based on push/augment and
410 
   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
411 411 
   \ref bunnagel98efficient.
412 
 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
413 
   capacity scaling \ref edmondskarp72theoretical.
414 
 - \ref CancelAndTighten The Cancel and Tighten algorithm
415 
   \ref goldberg89cyclecanceling.
416 
 - \ref CycleCanceling Cycle-Canceling algorithms
417 
   \ref klein67primal, \ref goldberg89cyclecanceling.
412 
 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
413 
   shortest path method \ref edmondskarp72theoretical.
414 
 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
415 
   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
418 416 

			




	419
	417
	
		
In general NetworkSimplex is the most efficient implementation,


			




	420
	418
	
		
but in special cases other algorithms could be faster.

			




        

    

    

    

        

            

                

                    lemon/capacity_scaling.h
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -66,7 +66,8 @@


			




	66
	66
	
		
  ///


			




	67
	67
	
		
  /// \ref CapacityScaling implements the capacity scaling version


			




	68
	68
	
		
  /// of the successive shortest path algorithm for finding a


			




	69
	
	
		
  /// \ref min_cost_flow "minimum cost flow". It is an efficient dual


			




	
	69
	
		
  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,


			




	
	70
	
		
  /// \ref edmondskarp72theoretical. It is an efficient dual


			




	70
	71
	
		
  /// solution method.


			




	71
	72
	
		
  ///


			




	72
	73
	
		
  /// Most of the parameters of the problem (except for the digraph)

			




        

    

    

    

        

            

                

                    lemon/cost_scaling.h
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -90,8 +90,10 @@


			




	90
	90
	
		
  /// finding a \ref min_cost_flow "minimum cost flow".


			




	91
	91
	
		
  ///


			




	92
	92
	
		
  /// \ref CostScaling implements a cost scaling algorithm that performs


			




	93
	
	
		
  /// push/augment and relabel operations for finding a minimum cost


			




	94
	
	
		
  /// flow. It is an efficient primal-dual solution method, which


			




	
	93
	
		
  /// push/augment and relabel operations for finding a \ref min_cost_flow


			




	
	94
	
		
  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,


			




	
	95
	
		
  /// \ref goldberg97efficient, \ref bunnagel98efficient. 


			




	
	96
	
		
  /// It is a highly efficient primal-dual solution method, which


			




	95
	97
	
		
  /// can be viewed as the generalization of the \ref Preflow


			




	96
	98
	
		
  /// "preflow push-relabel" algorithm for the maximum flow problem.


			




	97
	99
	
		
  ///


			




        

    






    
    



    


    

     
    
0 comments (0 inline)