zbMATH — the first resource for mathematics

The debts’ clearing problem: a new approach. (English) Zbl 1298.05305
Summary: The debts’ clearing problem is about clearing all the debts in a group of n entities (e.g. persons, companies) using a minimal number of money transaction operations. In our previous works we studied the problem, gave a dynamic programming solution solving it and proved that it is NP-hard. In this paper we adapt the problem to dynamic graphs and give a data structure to solve it. Based on this data structure we develop a new algorithm, that improves our previous one for the static version of the problem.
05C85 Graph algorithms (graph-theoretic aspects)
68P05 Data structures
90C39 Dynamic programming
PDF BibTeX Cite