Att hitta de anslutna komponenterna i en oriktad graf G = (V; E) på n = jV j hörn och m = jEj kanter är ett grundläggande beräkningsproblem. Den mest kända parallella algoritmen för CREW PRAM-modellen körs i O(log 2 n) tid med hjälp av n 2 = log 2 n processorer 6, 15]. För CRCW PRAM-modellen, där samtidig skrivning är tillåten, körs den mest kända algoritmen i O(log n) tid med något mer än (n + m) = log n processorer 26, 9, 5]. Simulera denna algoritm på den svagare CREW modellen ökar sin körtid till O(log 2 n) 10, 19, 29]. Vi presenterar här en enkel algoritm som körs i O(log 3=2 n) tid med n + m CREW processorer. Att hitta en o(log 2 n) parallell anslutningsalgoritm för denna modell var ett öppet problem under många år.
I ett genombrottsarbete presenterade Johnson och Metaxas REF en CREW algoritm som körs i O(log 3 2 n) tid med n + m processorer.
Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM
{'venue': 'J. Comput. Syst. Sci.', 'journal': None, 'mag_field_of_study': ['Computer Science']}