Znano je, da je minimiziranje spektralnega radija grafa z odstranjevanjem povezav NP-poln problem. Zato se je smiselno vprašati po hevrističnih strategijah reševanja tega problema. V tem članku je narejena primerjava nekaterih požrešnih metod. Dobljene so mejne vrednosti za zmanjševanje spektralnega radija. Pokazano je tudi, da je v večini primerov najboljša strategija metoda, ki odstrani povezavo l = i ~ j z največjim produktom (x1)_i (x1)_j i-te in j-te komponente lastnega vektorja x1.
COBISS.SI-ID: 1024376660
Ta znanstvena razprava, ki je objavljena v vrhunski splošni matematični reviji Proc. Lond. Math. Soc., reviji, ki po ARRS metodologiji sodi v kategorijo A', reši problem hamiltonskoti za družino kubičnih Cayleyjevih grafov grup glede na generatorsko množico, ki sestoji iz involucije, neinvolucije lihega reda in njenega inverza.
COBISS.SI-ID: 1024390740
V članku je obravnavan problem učinkovitega vrednotenja dane Boolove funkcije pri določenih, vendar neznanih vrednostih vhodnih spremenljivk. Z vsako spremenljivko x je povezan strošek c(x), ki ga je treba plačati, da izvemo vrednost x. Ob tem se pojavi vprašanje načrtovanja algoritmov, ki ob zaporednih poizvedbah o vrednostih spremenljivk izračunajo vrednost dane funkcije v neznanem vektorju, ob tem pa poskušajo zmanjšati nastale stroške. Kvaliteto algoritma ocenimo z uporabo konkurenčne analize, to je, z upoštevanjem razmerja med tem, kar algoritem plača, in med ceno najcenejše množice spremenljivk, ki so potrebni za določitev vrednosti funkcije v danem vektorju. Problem je povezan z dobro raziskanim področjem kompleksnosti odločitvenih dreves Boolovih funkcij, algoritmi za učinkovito vrednotenje Boolovih funkcij pa igrajo pomembno vlogo na številnih področjih, na primer v elektrotehniki (za analizo in načrtovanje preklopnih omrežjih), v umetni inteligenci, v medicini (testiranje bolnikov za bolezen), pri avtomatski diagnozi sistemov, v teoriji zanesljivosti, v teoriji iger in pri porazdeljenih računalniških sistemih, če jih omenimo le nekaj. V članku smo preučili t.i. ekstremno konkurenčno razmerje Boolovih funkcij. Izračunali smo prve netrivialne spodnje in zgornje meje za razrede Boolovih funkcij, ki niso vsebovani v razredu monotonih Boolovih funkcij. Za posebni primer simetričnih funkcij se meji ujemata in tako omogočata natančno opredelitev najboljše možne konkurenčnosti, ki jo more doseči deterministični algoritem. Podana zgornja meja je dosežena s preprostim polinomskim algoritmom.
COBISS.SI-ID: 1024267092