Prekrižno število je od Leightonovega dela »Complexity issues in VLSI« temeljni koncept pri študiju kompleksnosti elektronskih vezij. Izkaže pa se, da je ustreznejši pristop k minimiranju števila križišč v vezju ti. minorsko prekrižno število. Ta pristop namreč enakovredno obravnava vsa vozlišča v grafu, ki imajo enak električni potencial. V obravnavanem delu posplošimo tri Leightonove spodnje meje: prekrižno lemo, metodo z bisekcijo in metodo z vložitvami, na minorsko prekrižno število grafov. Utemeljimo tudi povezavo med minorskim prekrižnim številom in krivuljnimi grafi (string graphs).
COBISS.SI-ID: 15636057
V tem delu popolnoma opišemo neničelne pretoke v krepkih produktih grafov. V krepkem produktu vedno obstaja 2,3 ali 4 neničelni pretok in sicer 2 za Eulerjeve grafe, 4 za K4 drevesa in 3 za vse ostale. Uporabljena je konstrukcijska metoda, ki implicira tudi polinomski algoritem.
COBISS.SI-ID: 15616089
V članku dokažemo in prikažemo več rezultatov v zvezi z minor-minimalnimi grafi z minimalno stopnjo vsaj k. Glavni rezultati sledijo dvema smerema. Prva je konstrukcija minor-minimalnih grafov z minimalno stopnjo k iz ravno takšnih z minimalno stopnjo k-1, druga je dokaz bogate drevesne strukture, ki jih takšni grafi z naraščajočim k lahko imajo.
COBISS.SI-ID: 15813209
Kompleksna omrežja z veliko količino podatkov predstavljajo eno najbolj aktualnih fenomenov v informacijski družbi. V pričujoči monografiji so kompleksna omrežja predstavljena z različnih vidikov, posamezna poglavja pa so napisali vrhunski znanstveniki s svojih področij. Člani naše programske skupine smo prispevali poglavje o geodetskih množicah v grafih.
COBISS.SI-ID: 15720793
V delu je dokazano, da se da povezave vsakega grafa omejenega roda razbiti na vnaprej predpisano število delov (k), tako da ima kontrakcija kateregakoli od teh delov omejeno drevesno širino, kjer je meja odvisna le od števila k. Podoben, a precej enostavnejši rezultat, je znan za operacijo odstranjevanja povezav namesto kontrakcije (Baker 1994, Eppstein 2000 in drugi). Dobljeno dekompozicijo uporabimo za razvoj zelo splošnih (meta)algoritmov. Med drugim dobimo polinomske aproksimacijske sheme (PTAS) za poljubne probleme, ki so monotoni za kontrakcijo povezav.
COBISS.SI-ID: 15802457