Abstrakt. Med tanke på en Euclidean graf G i R d med n hörn och m kanter, vi anser att problemet med att lägga en kant till G sådan att sträckfaktorn för den resulterande grafen minimeras. För närvarande, den snabbaste algoritmen för att beräkna stretchfaktorn för en graf med positiva kantvikter körs i O(nm + n 2 log n) tid, vilket resulterar i en trivial O(n 3 m + n 4 log n)-tid algoritm för att beräkna den optimala kanten. Först visar vi att en enkel modifiering ger den optimala lösningen i O(n 4 ) tid med hjälp av O(n 2 ) utrymme. För att minska drifttiden överväger vi flera approximationsalgoritmer. Nyckelord. Beräkningsgeometri, approximationsalgoritmer, geometriska nätverk AMS ämnesklassificeringar. 65D18, 68U05, 68Q25 DOI. 10,1137/050635675 1. Inledning. Betrakta en uppsättning V av n punkter i R d. Ett nätverk på V kan modelleras som en oriktad graf G med vertex uppsättning V i storlek n och en kant uppsättning E i storlek m där varje kant (u, v) har en positiv vikt w (u, v). Ett Euclidean nätverk är ett geometriskt nätverk där vikten av eggen (u, v) är lika med Euclidean avstånd  och v mellan dess två endpoints u och v. För två hörn u, v i en viktad graf G vi använder δ G (u, v) för att beteckna en kortaste vägen mellan u och v i G, och längden på vägen betecknas av d G (u, v). Betrakta en viktad graf G = (V, E) och en graf G = (V, E ) på samma vertex set men med kant set E E. Vi säger att G är en t-spanner av G om för varje par hörn (u, v). Den minsta t sådan att G är en t-spanner för V kallas stretchfaktor, eller utvidgning, av G. Vi säger att en Euclidean nätverk G = (V, E) är en t-spanner om G = (V, E) är en t-spanner av det kompletta nätverket på V. Med andra ord, för två punkter p, q  och V grafavståndet i G är som mest t gånger Euclidean avstånd mellan de två punkterna. Fullständiga diagram utgör idealiska kommunikationsnät, men de är dyra att bygga; glesa skiftnycklar utgör billiga alternativ. Vikten av skiftnyckelnätet är ett mått på dess gleshet; andra gleshet åtgärder inkluderar antalet kanter, den maximala graden, och antalet Steiner punkter. Spannjorer för kompletta Euclidean grafer samt för godtycklig viktade grafer hitta applikationer i robotik, nätverk topologi design, distribuerade system, design av parallella maskiner, och många andra områden. Nyss hittade man intressanta praktiska tillämpningar
Farshi och Al. REF visar att det är möjligt att för en given geometrisk graf beräkna den kant som resulterar i den största utvidgningsminskningen av O(n 4) tiden.
Improving the Stretch Factor of a Geometric Network by Edge Augmentation
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}