Patcas, Csaba (2012) The debts' clearing problem's relation with complexity classes. ACTA MATHEMATICA ACADEMIAE PAEDAGOGICAE NYÍREGYHÁZIENSIS, 28 (2). pp. 217-226. ISSN 0866-0174
|
Text
28_21.pdf Download (716kB) | Preview |
Official URL: http://www.emis.de/journals/AMAPN/index.html
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | debt clearing, NP-hard, NP-easy, minimum edge-cost flow |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | Zsolt Baráth |
| Date Deposited: | 05 Feb 2024 08:15 |
| Last Modified: | 05 Feb 2024 08:20 |
| URI: | http://real.mtak.hu/id/eprint/187560 |
Actions (login required)
 |
Edit Item |
