Vi presenterar en algoritm för att beräkna alla par Kortaste Paths (APSP) av ett nätverk på ett distribuerat sätt. Modellen för distribuerad beräkning anser vi är den meddelande passerar modell: i varje synkron runda, varje nod kan överföra en annan (men kort) meddelande till var och en av sina grannar. Vi tillhandahåller en algoritm som beräknar APSP i O(n) kommunikationsrundor, där n betecknar antalet noder i nätverket. Detta innebär en linjär tidsalgoritm för beräkning av ett näts diameter. På grund av en lägre bundet dessa två algoritmer är optimal upp till en logaritmisk faktor. Dessutom presenterar vi en ny nedre gräns för approximering av diametern D i en graf: Att få svara på D+1 eller D kan påskynda beräkningen med högst en faktor D. På den positiva sidan ger vi en algoritm som uppnår en sådan hastighetsökning av D och beräknar en 1 + ε multiplicativ approximation av diametern. Vi utökar dessa algoritmer för att beräkna eller approximera andra problem, såsom omkrets, radie, centrum och perifera hörn. I hjärtat av dessa approximationsalgoritmer är S-Shortest Paths problem som vi löser i O (-) + D tid.
Denna algoritm är en ändring av S-Shortest Paths algoritm av REF.
Optimal distributed all pairs shortest paths and applications
{'venue': "PODC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}