Detta dokument introducerar konceptet med genvägar med låg belastning för (nära)planära nätverk, och visar sin kraft genom att använda dem för att få nästan optimala distribuerade algoritmer för problem som Minimum Spanning Tree (MST) eller Minimum Cut, i planar nätverk. Tänk på en graf G = (V, E) och en uppdelning av V i undergrupper av noder S1,. ., SN, varje inducerar en ansluten del G [Si]. Vi definierar en α-överbelastning genväg med dilatation β att vara en uppsättning subgrafer H1,. .., HN G, en för varje delmängd Si, sådan att 2. För varje kant är antalet delgrafer G[Si] + Hej innehållande e högst α. Vi bevisar att varje partition av en D-diameter planar graf i individuellt anslutna delar medger en O(D log D)-överbelastning genväg med dilation O(D log D), och vi presenterar också en distribuerad konstruktion av det i Õ(D) rundor. Vi bevisar dessutom att dessa parametrar är nära optimala, d.v.s. det finns fall där, oundvikligen, max{α, Slutligen använder vi genvägar med låg belastning, och deras effektiva distribuerade konstruktion, för att härleda Õ(D)-runda distribuerade algoritmer för MST och Min-Cut, i plana nätverk. Denna komplexitet motsvarar nästan den triviala nedre gränsen för  och D. Vi noterar att detta är det första resultatet som förbigår den välkända (D+ ε n) existentiella nedre gränsen för allmänna grafer (se Peleg och Rubinovitj [FOCS'99], Elkin [STOC'04] och Das Sarma et al. [STOC'11]) i en familj av diagram av intresse.
Särskilt kan de idéer som finns i REF omvandlas till mycket korta och rena Õ(D + ε n) runda algoritmer för allmänna grafer, och nära-optimala Õ(D) runda algoritmer för speciella klasser av grafer, för problem som MST och Min-Cut.
Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and Min-Cut
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}