Acta Mathematica Academiae Paedagogicae Nyíregyháziensis, Vol. 28, No. 2, pp. 217-226 (2012)

The debts' clearing problem's relation with complexity classes

Csaba Patcas

Babes-Bolyai University

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. In a previous paper we conjectured the problem to be NP-complete. In this paper we prove that it is NP-hard in the strong sense and also NP-easy. We also show the same results for a restricted version of the problem.

Keywords: debt clearing, NP-hard, NP-easy, minimum edge-cost flow

Classification (MSC2000): 68Q17; 05C21

Full text of the article:

[Previous Article] [Contents of this Number]
© 2013 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition