Fast recognition of partial star products and quasi cartesian products - Hellmuth, Marc (Ars mathematica contemporanea, 2015)
Č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 ?$δ^*$?, katere konveksno zaprtje nam da produktno relacijo ?$δ$?, 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 ?$δ^*$? za grafe z maksimalno omejeno stopnjo. Nadalje, definiramo kvazi kartezične produkte kot grafe z netirivialnim ?$δ^*$?. 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.
Keywords: approximate product; aproksimativni produkt; Cartesian product; grafovski sveženj; graph bundle; kartezični produkt; kvazi produkt; parcialno zvezdni produkt; partial star product; product relation; produktna relacija; quasi product