Motiverade delvis av praktiska överväganden. Bland de många områden som behandlats i den senaste litteraturen är sortering [2, 3, 7, 12, 15], utvärdering av aritmetiska uttryck, linjära upprepningar och polynom [4, 8, 10], matrisalgoritmer [5, 6, 13], och grafteori [9, 14, 15]. I detta papper presenterar vi en parallell algoritm CONNECT som bestämmer de anslutna komponenterna i en oriktad graf med n hörn i tiden O (log2n) med n 2 processorer. Därefter modifierar vi algoritmen för att demonstrera en observation på grund av F.P. Preparata och R.L. Probert, viz., n[n/lg n] processorer 1 räcker för att uppnå en tidsgräns för O(log2n). Slutligen visar vi att CONNECT kan ändras för att beräkna den transitiva stängningen av en nxn-symmetrisk boolesk matris i tid O(log2n) med hjälp av n[n/lg n] processorer. Vi använder den enda instruktion stream-multiple data stream (SIMD) modellen av parallella processorer. Det antas att processorn har tillgång till ett gemensamt minne och att samtidig åtkomst till samma plats är tillåten för hämta instruktioner men inte för förvaringsanvisningar. Vi presenterar en parallell algoritm som använder n 2 processorer för att hitta de anslutna komponenterna i en oriktad graf med n hörn i tiden O(log2n). En O0og2n) tidsbindning kan också uppnås med endast n[n/[log2n]-processorer. Algoritmen kan han använda för att hitta den övergående stängningen av en symmetrisk boolesk matris. Vi antar att processorn har tillgång till ett gemensamt minne. Samtidigt tillträde till samma plats är tillåtet för hämta instruktioner men inte för förvaringsanvisningar.
Parallella algoritmer : Hirschberg, Chandra och Sarwate REF presenterade en O(log 2 n) tid parallellalgoritm med hjälp av n 2 /logn processorer på en CREW PRAM för att hitta anslutna komponenter i en oriktad graf.
Computing connected components on parallel computers
{'venue': 'CACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}