Group:Grad-student Theory Lunch
Title: Two-hop Connected Dominating Set(2hop-CDS) Problem on Unit Disk Graph(UDG)
Speaker: Wei Hu, Kai Jin, Xiang Zhang Tsinghua university
Time: 2010-05-06 12:00-2010-05-06 13:30
Venue: FIT 1-222


Presenter: Wei Hu

I will talk about the 2hop Connected Dominating Set(2hop-CDS) Problem on unit disk graph(UDG).

Let G(V, E) be a undirected graph. Dominating Set(DS) of G is a set of vertices U such that for all v \in V/U there exists u \in U that (v, u) \in E. If U is connected we call it connected dominating set(CDS). 2hop-CDS is defined base on CDS. Let p(u, v) be the shortest path and |p(u, v)| be the number of edges of the path. We call it 2hop-CDS if for all p(u, v) that |p(u, v)|=2 the middle vertice must be in the CDS.

In general graph there is O(log(\delta)) approximation algorithm [ICDCS 09] where \delta stands for the maximum degree of node. I am interested in the problem on Unit disk graph. We want to do the following things:

(i) 2hop-CDS on UDG is in NP-complete

(ii) Find a constant approximation algorithm for 2hop-CDS on UDG

The reason that we consider it on UDG is that UDG has a good combinatorial properties. I will present to you some of the ideas which we tried but failed.


Presenter: Kai Jin

This time I will talk on a computational geometry problem called Maximal Parallelogram Problem. Its goal is finding a maximum area parallelogram inside a given convex polygon. It arises from a simple case of tolerant geometry facility location problem. There is a lot of previous work on finding extremal figures inside or inscribed in polygons. For example, the first linear time algorithm for finding maximum area triangle is given by [DS]. There are also many new papers in this subject in the main CG conferences in the recent years.

In this problem, the first challenge is related to the fact that the maximal parallelogram may not lie on the vertices of the given polygon. So there is non-trivial brute-force algorithm for solving it. I have proved some structural properties of the maximal parallelogram and I've given a polynomial time algorithm for this problem (this algorithm relies on these geometric properties).

Recently, I also made some progress on this problem. By a further analysis of my previous lemmas, it is now very clear how to give an O(n^3) time algorithm.

MAIN POINT OF MY TALK: And it is even possible to be solved in O(n^2) time as long as a special subproblem can been settled. I will introduce this subproblem to you, and I 'll appreciate any suggestions on how to resolve my conjecture.

[BDDG]James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, and Leo J. Guibas, Finding Extremal Polygons, SIAM J. Comput. Volume 14, Issue 1, pp. 134-147 (1985) [DS]Dobkin, D. P., and Snyder, L. On a General Method for Maximizing and Minimizing Among Certain Geometric Problems. 20th IEEE Symposium on the Foundations of Computer Science, 1979, 9-17.

Short Bio: