Tuesday, February 9th, 2010
A Disk Graph is an intersection of set of disks in the Euclidean plane. They are mostly used to model telecommunications systems. We assume that each transmitter/receiver has a circle of certain diamater area of effect. Disk graphs are one of the well studied class of graphs in the literature. For different graph theoretical problems(stable set, vertex coloring, clique) results are available in the literature. Most of the problems are NP-hard. In my report, I am mainly focused on approximation algorithms for disk graphs. There exist also a presentation file created by using Latex/Beamer.
Tags: Approximation Algorithms, Beamer, Graph Theory
Posted in Optimization | No Comments »