Abstrakt. Beroende på om dubbelriktade länkar eller enkelriktade länkar används för kommunikation, är nätverkstopologin under en given områdestilldelning antingen en oriktad graf som kallas dubbelriktad topologi, eller en riktad graf som kallas enkelriktad topologi. Min-Power dubbelriktad (resp., enkelriktad) k-Node Anslutningsproblem söker en räckvidd tilldelning av minsta totala effekt under den begränsning som den producerade dubbelriktade (resp. enkelriktad) topologi är k-vertex ansluten. På samma sätt, Min-Power dubbelriktad (resp., enkelriktad) k-Edge Anslutningsproblem söker en räckvidd tilldelning av minsta totala effekt som omfattas av begränsningen den producerade dubbelriktade (resp., enkelriktad) topologi är k-kanten ansluten. Problemet Min-Power Bidirective Biconnectivity och problemet Min-Power Bidirective Edge-Biconnectivity har undersökts av Lloyd et al. [23]................................................................. De visar att områdestilldelningen baserat på approximationsalgoritmen för Khuller och Raghavachari [18], som vi kallar Algoritm KR, har en approximationsgrad på högst 2.2 -2/n(2 + 1/n) för Min-Power Bidirective Biconnectivity, och områdestilldelning baserad på approximationsalgoritmen för Khuller och Vishkin [19], som vi kallar Algorithm KV, har en approximationsgrad på högst 8.1 -1/n för Min-Power Bidirective Edge-Biconnectivity. I detta dokument etablerar vi först NP-hårdheten i Min-Power Bidirective (Edge-) Biconnectivity. Då visar vi att Algorithm KR har en approximationsgrad på högst 4 för både Min-Power Bidirective Biconnectivity och Min-Power Unidirective Biconnectivity, och Algorithm KV har en approximationsgrad på högst 2k för både Min-Power Bidirective k-Edge Connectivity och Min-Power Unidirective k-Edge Connectivity. Vi föreslår också en ny enkel konstant-uppskattning algoritm för både Min-Power dubbelriktad Bikonnektivitet och Min-Power enkelriktad Bikonnektivitet. Denna nya algoritm gäller endast Euclidean instanser, men är bäst lämpad för distribuerat genomförande.
Calinescu m.fl. REF förbättrar approximationsresultatet för k-edge-anslutning till 2k och för bikonnektivitet till 4.
Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks
{'venue': 'MONET', 'journal': None, 'mag_field_of_study': ['Computer Science']}