Local solutions for global problems in wireless networks (Q2466005)

The author reviews the basic mathematical structures that develop local algorithms in unit distance wireless (UDW) networks. The problems reviewed are the following: Given a connected UDW network, can a local algorithm be designed to extract a connected planar subgraph from it? Can a connected subgraph of a UDW network be obtained such that the weight of the graph is close to the weight of the minimum weight spanning tree of the UDW network? The author also presents two new algorithms. The first colours the edges of a planar subgraph of a network, and the second obtains small dominating sets of vertices. These algorithms are local, and use a novel technique of tilings of the plane.