2026-07-20T05:04:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1027 2024-03-06T11:07:12Z ddc:004 open_access

Power Assignment in Radio Networks with Two Power Levels Carmi, Paz Katz, Matthew Radio networks power assignment approximation algorithms minimum spanning tree disk graph We study the power assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges - short and long. We show that this problem is NP-hard, and present an O(n^2)-time assignment algorithm, such that the number of transmitters that are assigned long range by the algorithm is at most (11/6) times the number of transmitters that are assigned long range by an optimal algorithm. We also present an (9/5)-approximation algorithm for this problem whose running time is considerably higher. Next, we formulate and study the Minimum-Area Spanning Tree (MAST)problem: Given a set P of n points in the plane, find a spanning tree of P of minimum "area," where the area of a spanning tree T is the area of the union of the n-1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constant-factor approximation for MAST. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (MARA) problem, for the Minimum-Area Connected Disk Graph (MACDG) problem, and for the Minimum-Area Tour (MAT) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paz Carmi and Matthew Katz 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06481.3 urn:nbn:de:0030-drops-10277 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.3 eng https://creativecommons.org/licenses/by/4.0/legalcode