Huvudfokus i detta dokument är analysen av en enkel randomiserad plan för att bygga låg vikt k-anslutna spännvidd subgrafer. Vi visar först att vårt schema ger en enkel approximation algoritm för att konstruera en minsta vikt k-ansluten spännvidd subgraph i en viktad komplett graf, ett NP-hård problem även om vikterna uppfyller triangeln ojämlikhet. Vi visar att vår algoritm ger ett approximationsförhållande av O(k log n) för en metriska graf, O(k) för en slumpmässig graf med noder jämnt slumpmässigt fördelade i [0, 1] 2 och O(log n k ) för en komplett graf med slumpmässiga kantvikter U (0, 1). Vi visar att vårt system är optimalt med avseende på den mängd "lokal information" som behövs för att beräkna någon ansluten spännvidd subgraf. Vi visar sedan att vårt schema kan tillämpas för att utforma en effektiv distribuerad algoritm för att konstruera en sådan ungefärlig k-ansluten spännviddsdel (för alla k ≥ 1) i en punkt-till-punkt distribuerad modell, där processorer bildar ett komplett nätverk. Vår algoritm tar O(log n k ) tid och förväntade O(nk log n k ) meddelanden. Vårt resultat i samband med ett resultat av Korach et al. ([21]) innebär att den förväntade meddelande komplexiteten hos vår algoritm är betydligt bättre än den bästa distribuerade algoritmen som hittar en optimal k-ansluten subgraf. Vi visar också att för de geometriska instanserna, vår randomiserade schema konstruerar låggradig k-anslutna spännvidd subgrafer som har O (k log n) maximal grad, med hög sannolikhet.
Analysen av ett enkelt randomiserat system för konstruktion av lågviktiga Kconnected spanning sub-grafer ges av REF.
A Simple Randomized Scheme for Constructing Low-Weight k-Connected Spanning Subgraphs with Applications to Distributed Algorithms
{'venue': 'FOCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}