Krepka klika v grafu je klika, ki ima neprazen presek z vsako maksimalno neodvisno možico. Članek predstavlja prvo obširno študijo t.i. lokalizabilnih grafov, ki so definirani kot grafi, katerih množico točk je mogoče razdeliti na paroma disjukntne krepke klike. Ta lastnost je bila omenjena v zaključnih opombah članka Yamashite in Kamede (Networks, 1999), motiviranega z vprašanji s področja porazdeljenega računanja, in predstavlja pomemben - in za popolne grafe edini - način, kako doseči, da je graf dobro pokrit (tj. da so vse maksimalne neodvisne množice enako velike). V članku so dosežene številne karakterizacije lokalizabilnih grafov. Razviti so učinkoviti algoritmi za prepoznavanje te lastnosti v grafih brez trikotnikov, C_4-prostih grafih in povezavnih grafih. Z uporabo lokalizabilnih grafov smo ovrgli domnevo Zaare-Nahandija o k-delnih dobro pokritih grafih, v katerih so vse maksimalne klike velikosti k.
COBISS.SI-ID: 1540211908
Množica točk D v grafu G je učinkovita dominantna množica, če je vsaka točka grafa dominirana z natanko eno točko v množici D. Problem učinkovite dominacije (UD) je določiti, ali dan graf vsebuje učinkovito dominantno množico. Graf G je H-prost za nek graf H, če G ne vsebuje induciranega podgrafa, izomorfnega grafu H. Problem UD je NP-poln tudi za številne posebne razrede grafov, npr. za K_{1,3}-proste grafe in za 2P_3-proste grafe. Znana je dihotomija glede časovne zahtevnosti utežene različice problema (UUD) za H-proste grafe. Za (H_1,H_2)-proste grafe pa je to vprašanje še odprto. Glavni rezultati članka so: (1) izboljšava časovnih zahtevnosti polinomskih algoritmov za problem UUD za nekatere H-proste grafe in poenostavitev dokazov z uporabo modularne dekompozicije; (2) študij zahtevnosti problema UUD za nekatere primere (H_1, H_2)-prostih grafov.
COBISS.SI-ID: 1540387780
ISK4 v grafu G je induciran podgraf grafa G, izomorfen subdiviziji polnega grafa na 4 točkah. Kolo je graf, ki sestoji iz cikla in še ene točke, ki ima na ciklu vsaj tri sosede. Pravimo, da je graf {ISK_4,kolo}-prost, če ne vsebuje nobenega ISK4 in ne vsebuje induciranega podgrafa, izomorfnega kakšnemu kolesu. V članku razvijemo algoritem časovne zahtevnosti O(|V(G)|^7), ki v danem točkovno-uteženem grafu G poišče neodvisno množico največje možne teže.
COBISS.SI-ID: 17896793
V članku je opravljen sistematičen študij računske zahtevnosti povezane različice treh medsebojno povezanih problemov transverzal v grafih: problem točkovnega pokritja, problem povratne množice točk in problem transverzale lihih ciklov. Tako kot originalne različice problemov so tudi ti problemi NP-polni za splošne grafe. Graf G je H-prost za nek graf H, če G ne vsebuje induciranega podgrafa, izomorfnega grafu H. Znano je, da je problem najmanjšega povezanega točkovnega pokritja NP-poln celo za razred H-prostih grafov, če H vsebuje K_{1,3} ali cikel. Pokazali smo, da tudi drugi dva "povezana" problema ostaneta NP-polna pod tovrstnimi omejitvami. Pokazali smo, da so za vsako naravno število s problemi najmanjšega povezanega točkovnega pokritja, najmanjše povezane povratne množice točk in najmanjše povezane transverzale lihih ciklov rešljivi v polinomskem času v razredu sP_2-prostih grafov. Za dokazovanje teh rezultatov smo uporabili znane rezultate o ceni povezanosti za točkovna pokritja, povratne množice točk in transverzale lihih ciklov. To je prva uporaba cene povezanosti, ki vodi do algoritmov polinomske časovne zahtevnosti.
COBISS.SI-ID: 18180441
Motivirani z aplikacijami v genomskih študijah rakastih tvorb in po delu Hajirasoulihe in Raphaela (WABI 2014) so Hujdurović idr. (IEEE TCBB, 2018) uvedli problem najmanjšega nekonfliktnega razcepa vrstic (NNRV): razcepi vsako vrstico dane binarne matrike v bitni OR nove množice vrstic, tako da dobljena matrika ustreza pogoju popolne filogenije in ima najmanjše možno število vrstic med vsemi matrikami s to lastnostjo. Hajirasouliha in Raphael sta predlagala tudi študijo podobnega problema, pri katerem je naloga zmanjšati število paroma različnih vrstic nastale matrike. Hujdurović et al. so dokazali, da sta oba problema NP-težka, podali s problemoma povezano karakterizacijo tranzitivno usmerljivih grafov in predlagali hevristični algoritem polinomske časovne zahtevnosti za problem NNRV, ki temelji na barvanjih grafov primerljivosti. V članku podamo novi, preglednejši formulaciji obeh problemov, s čimer pokažemo, da sta problema ekvivalentna dvema optimizacijskima problemoma na vejitvah v izpeljanem usmerjenem acikličnem grafu. Na podlagi teh formulacij izpeljemo nove rezultate, vključno z naslednjimi: (1) izboljšava hevristike Hujdurovića idr. z uporabo novega min-max rezultata v usmerjenih grafih, ki je utežena posplošitev Dilworthovega izreka, (2) rezultati o APX-težkosti za oba problema; (3) aproksimacijski algoritmi; in (4) algoritma eksponentne časovne zahtevnosti, ki problema rešita do optimalnosti hitreje kot z naivnim pristopom. Raziskave v članku so povezane s številnimi dobro preučenimi koncepti v kombinatorični optimizaciji: particije delno urejenih množic na verige, laminarni hipergrafi in (klasična in utežena) barvanja grafov.
COBISS.SI-ID: 1540282052