Detta papper behandlar den grundläggande frågan om hur väl ett träd kan ungefärliga avstånd av ett metriska utrymme eller en graf. Med tanke på en graf är problemet med att bygga ett spännträd i en graf som starkt bevarar avstånden i grafen ett grundläggande problem i nätverksdesignen. Vi presenterar skalförvrängningar inbäddade där förvrängningen skalar som en funktion av, Med garantin att för varje förvrängning av en bråkdel 1 - av alla par begränsas därefter. En sådan begränsning innebär i synnerhet att den genomsnittliga snedvridningen och snedvridningen är liten. Specifikt, våra inbäddningar har konstant genomsnittlig förvrängning och O ( ε log n) 2 - förvrängning. Detta följer av följande resultat: vi bevisar att varje metriska utrymme inbäddas i en ultrametrisk med skalförvrängning O( 1/ ). För grafinställningen visar vi att alla viktade grafer innehåller ett spännträd med skalförvrängning O( 1/ ). Dessa gränser är tighta även för inbäddning i godtyckliga träd. För probabilistisk inbäddning i spännande träd visar vi en skalförvrängning av Õ(log 2 (1/ )), vilket innebär konstant qdistortion för varje fast q < ∞.
Nyligen ger REF en inbäddning från en viktad graf till ett av dess spännande träd, vars genomsnittliga förvrängning över alla par är konstant.
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
{'venue': "SODA '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}