TY - GEN

T1 - Local PTAS for independent set and vertex cover in location aware unit disk graphs (Extended Abstract)

AU - Wiese, Andreas

AU - Kranakis, Evangelos

PY - 2008

Y1 - 2008

N2 - We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting. The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.

AB - We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting. The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.

UR - http://www.scopus.com/inward/record.url?scp=45849086914&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-69170-9_28

DO - 10.1007/978-3-540-69170-9_28

M3 - Conference contribution

AN - SCOPUS:45849086914

SN - 3540691693

SN - 9783540691693

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 415

EP - 431

BT - Distributed Computing in Sensor Systems - 4th IEEE International Conference, DCOSS 2008, Proceedings

T2 - 4th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2008

Y2 - 11 June 2008 through 14 June 2008

ER -