Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • Fast recognition of partial star products and quasi cartesian products
    Hellmuth, Marc ; Imrich, Wilfried ; Kupka, Tomas
    Članek obravnava hitro računanje relacije ▫$\mathfrak{d}$▫ na množici povezav povezanih grafov, ki igra odločilno vlogo pri prepoznavanju aproksimativnih kartezičnih produktov, pri šibki ... rekonstrukciji kartezičnih produktov in pri prepoznavanju svežnjev kartezičnega grafa z bazo brez trikotnikov. Poseben primer relacije ▫$\mathfrak{d}$▫ je relacija ▫$\delta^\ast$▫, katere konveksno zaprtje nam da produktno relacijo ▫$\delta$▫, ki inducira prafaktorsko dekompozicijo povezanih grafov glede na kartezični produkt. Za konstrukcijo ▫$\mathfrak{d}$▫ so posebej zanimivi t.i. parcialni zvezdni produkti. Z uporabo različnih posebnih podatkovnih struktur lahko izračunamo parcialne zvezdne produkte v konstantnem času. Ti izračuni so uglašeni s prepoznavanjem aproksimativnih grafovskih produktov, vodijo pa tudi k algoritmu, ki v linearnem času izračuna ▫$\delta^\ast$▫ za grafe z maksimalno omejeno stopnjo. Nadalje, definiramo kvazi kartezične produkte kot grafe z netirivialnim ▫$\delta^\ast$▫. Podamo več primerov in pokažemo, da lahko pri grafih z omejeno maksimalno stopnjo kvazi kartezične produkte prepoznamo v linearnem času. Nazadnje omenimo, da lahko kvazi produkte prepoznamo v sublinearnem času s paraleliziranim algoritmom.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 9, no. 2, 2015, str. 223-242)
    Vrsta gradiva - članek, sestavni del
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 17605721

    Povezava(-e):

    http://amc-journal.eu/index.php/amc/article/download/520/726
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 9, no. 2, 2015, str. 223-242)

loading ...
loading ...
loading ...

Vnos na polico