
doi: 10.1007/11604686_31
We consider several graph theoretic problems on unit disk graphs (Maximum Independent Set, Minimum Vertex Cover, and Minimum (Connected) Dominating Set) relevant to mobile ad hoc networks. We propose two new notions: thickness and density. If the thickness of a unit disk graph is bounded, then the mentioned problems can be solved in polynomial time. For unit disk graphs of bounded density, we present a new asymptotic fully-polynomial approximation scheme for the considered problems. The scheme for Minimum Connected Dominating Set is the first Baker-like asymptotic FPTAS for this problem. By adapting the proof, it implies e.g. an asymptotic FPTAS for Minimum Connected Dominating Set on planar graphs.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 17 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
