Geometry based heuristics for unit disk graphs

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

19 pages

Scientific paper

Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and to intersection graphs of higher dimensional regular objects.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Geometry based heuristics for unit disk graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Geometry based heuristics for unit disk graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometry based heuristics for unit disk graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-635599

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.