Vi överväger hur man tilldela etiketter till någon oriktad graf med n noder sådan att, med tanke på etiketter av två noder och ingen annan information om grafen, det är möjligt att bestämma avståndet mellan de två noderna. Utmaningen i ett sådant avstånd märkning system är främst att minimera den maximala etiketten längd och sekundärt att minimera den tid som behövs för att svara på avstånd frågor (avkodning). Tidigare system har erbjudit olika avvägningar mellan etikettlängder och frågetid. Detta dokument presenterar en enkel algoritm med kortare etiketter och kortare frågetid än någon tidigare lösning, vilket förbättrar state-of-the-art med avseende på både etikettlängd och frågetid i en enda algoritm. Vår lösning tar upp flera öppna problem med etikettlängd och avkodningstid och är den första förbättringen av etikettlängd i mer än tre decennier. Mer specifikt presenterar vi ett avståndsmärkningssystem med etiketter på längdlogg 3 2 n + o(n) bitar 1 och konstant avkodningstid. Detta överträffar alla befintliga resultat med avseende på både storlek och avkodningstid, inklusive Winklers (Combinatorica 1983) tioåriga resultat, som använder etiketter av storlek (log 3)n och O(n/ log n) avkodningstid, och Gavoille et al. (SODA'01), som använder etiketter av storlek 11n + o(n) och O(log log n) avkodningstid. Dessutom är vår algoritm enklare än de tidigare. I fallet med integrerad kant vikter av storlek som mest W, Vi presenterar nästan matchande övre och nedre gränser för etiketten storlek l: 2 n log (2W + 1) + O(log n · log(nW ) ). Dessutom, för r-additive approximation märkningssystem, där avstånd kan vara av med upp till en additiv konstant r, presenterar vi både övre och nedre gränser. I synnerhet presenterar vi en övre gräns för 1-additive approximationssystem som i det oviktade fallet har samma storlek (till skillnad från andra ordertermer) som ett adjacenssystem, nämligen n/2. Vi ger också resultat för bipartitgrafik samt för exakta och 1-additiva avstånd orakel.
En översikt över avståndsmärkningssystem finns i REF.
Simpler, faster and shorter labels for distances in graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}