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
Ignore white space 6 line context
... ... 
@@ -407,13 +407,11 @@
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,

			




        

    

    

    

        

            

                

                    lemon/capacity_scaling.h
                

                

                  
                  
                  
                  Ignore white space
                  4 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -67,5 +67,6 @@


			




	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
	
		
  ///

			




        

    

    

    

        

            

                

                    lemon/cost_scaling.h
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -91,6 +91,8 @@


			




	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.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)