The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

  
       
         
    STUDIA INFORMATICA - Issue no. 2 / 2009  
         
  Article:   ON THE DEBTS’ CLEARING PROBLEM.

Authors:  CSABA PĂTCAŞ. 		 
       
         
  Abstract:  The debts’ clearing problem is about clearing all the debts in a group of n entities (eg. persons, companies) using a minimal number of money transaction operations. First we will model the problem using graph theoretical concepts and we will reduce the problem to a minimum cost maximum ow problem in a bipartite graph. Because our cost function is not the usual one, a classical minimum cost maximum ow algorithm cannot be applied in this case. We propose a solution using the dynamic programming method with Θ(2n) space and exponential time complexity. We will also examine other solving possibilities.

Key words and phrases. NP-completeness, dynamic programming, network flow.
  
         
     
         
         
      Back to previous page