0 KB308 KB23 KB200820252013DeLaVina, ErmelindaLarson, Craig Erikštevilka:2letnik:6str. 237-245COBISSID:16473945ISSN:1855-3966URN:URN:NBN:SI:doc-HBUXQVS6enDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneacritical independence numbercritical independent setgraph theoryindependence numberKönig-Egerváry graphmatching numberteorija grafovA parallel algorithm for computing the critical independence number and related sets|An independent set ?$I_c$? is a critical independent set if ?$|I_c| - |N(I_c)| \ge |J| - |N(J)|$?, for any independent set ?$J$?. The critical independence number of a graph is the cardinality of a maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. The existing algorithm runs in ?${\mathcal O}\left( n^{2.5}\sqrt{(m/\log n}\right)$? time for a graph ?$G$? with ?$n = |V(G)|$? vertices and ?$m$? edges. It is demonstrated here that there is a parallel algorithm using ?$n$? processors that runs in ?${\mathcal O}\left( n^{1.5} \sqrt{(m/\log n}\right)$? time. The new algorithm returns the union of all maximum critical independent sets. The graph induced on this set is a König-Egerváry graph whose components are either isolated vertices or which have perfect matchingsTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije