Algorithms for Geometric Networks

Geometric Networks typically are a sparse subgraphs of a complete graph defined over a set of points embedded in the plane (or space). There are several algorithms which take a complete graph and compute a sparse subgraph satisfying various constraints, e.g. low diameter, constant degree and fault-tolerant. In our recent work, we have designed algorithms which compute sparse subgraphs of non-complete graphs. Especially, given a k-partite graph, we construct a sparse subgraph consisting of linear number of edges, and show that the shortest path gets stretched by a constant factor. This result has appeared in SIAM Jl. Computing 38 (5): 1803—1820, 2009. We want to further broaden the scope of this work with the help of a global link student in the following directions (a) Implementation (b) Experimental Study (c) Possibly come up with an algorithm that constructs a planar subgrap

Student is first expected to learn the techniques used in the research mentioned above. Then the student is expected to implement an algorithm, and do an experimental study. If time permits, the student will be mentored to design an algorithm to compute sparse planar subggraphs.

Faculty Supervisor:

Dr. Anil Maheshwari

Student:

Amit Gupta

Partner:

Discipline:

Computer science

Sector:

Information and communications technologies

University:

Carleton University

Program: