Vi presenterar en deterministisk distribuerad algoritm för att beräkna allapar kortaste vägar (APSP) i en kantvägd riktad eller oriktad graf. Vår algoritm körs i Õ (n 3/2 ) rundor i den överbelastade modellen, där n är antalet noder i grafen. Detta är den första o(n 2 ) rundor deterministisk distribuerad algoritm för viktade APSP problem. Vår algoritm är ganska enkel och innehåller en deterministisk distribuerad algoritm som vi utvecklar för att beräkna en 'blocker set' [14], som har använts tidigare i sekventiell dynamisk beräkning av APSP.
En helt deterministisk algoritm för att lösa APSP i viktade grafer i Õ(n 3/2 ) rundor har dykt upp i REF.
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
{'venue': "PODC '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}