Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi

Monte-Carlo randomized algorithm for minimum feedback arc set (CROSBI ID 224189)

Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija

Kudelić, Robert Monte-Carlo randomized algorithm for minimum feedback arc set // Applied soft computing, 41 (2016), 235-246. doi: 10.1016/j.asoc.2015.12.018

Podaci o odgovornosti

Kudelić, Robert

engleski

Monte-Carlo randomized algorithm for minimum feedback arc set

When we are developing information system we must, in some way, determine the development order of its subsystems. Currently, this problem is not formally solved. Therefore, to rectify this we are proposing a solution which takes the sum of weights of feedback arcs as a criteria for determining the development order, rather than some other criteria that has not come directly from information system description. For the purpose of solving this problem we have developed, analyzed, and tested, Branch and Bound algorithm and Monte-Carlo randomized algorithm which solves the problem of Information System Subsystems Development Order in polynomial time with arbitrary probability. Also, we have determined an approximation error for developed Monte-Carlo randomized algorithm. Lastly, we have proven that the problem of Information System Subsystems Development Order is NP-hard, NP-complete, and APX-hard.

Minimum feedback arc set ; Monte Carlo ; Randomization ; NP-hard ; NP-complete ; APX-hard

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

Podaci o izdanju

41

2016.

235-246

objavljeno

1568-4946

10.1016/j.asoc.2015.12.018

Povezanost rada

Računarstvo, Informacijske i komunikacijske znanosti

Poveznice
Indeksiranost