Approximation Algorithms for Unit Disk Graphs | Zendy

Erik Jan van Leeuwen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Approximation Algorithms for Unit Disk Graphs

Author(s) -

Erik Jan van Leeuwen

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-31000-2

DOI - 10.1007/11604686_31

Subject(s) - unit disk graph , vertex cover , dominating set , unit disk , polynomial time approximation scheme , bounded function , connected dominating set , approximation algorithm , maximal independent set , planar graph , vertex (graph theory) , computer science , independent set , mathematics , discrete mathematics , graph , combinatorics , chordal graph , 1 planar graph , wireless network , telecommunications , mathematical analysis , wireless

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research