Investigators on Indian Side: Kavitha Telikepalli, Jaikumar Radhakrishnan, Prahladh Harsha

Investigators on German Side: Kurt Mehlhorn, Julian Mestre, Chinmoy Dutta, Chien-Chung Huang, Tomasz Jurkiewicz

Broad area of research:

The focus of the research group at TIFR is to design efficient algorithms for several graph problems, to understand the behaviour of "natural algorithms", and to study combinatorial and algorithmic questions relating to hypergraph colouring, datastructures, and streaming. Some of the particular problems that we have been working and will be working on as a part of IMPECS are matching problems in graphs (both in bipartite graphs and general graphs). One model is that of weighted graphs where the edge weights denote the importance of including the edge in the matching and the goal is to compute maximum weight matchings more efficiently. Another model is where each edge has 2 ranks: how each endpoint ranks the other endpoint as a partner and the goal here is to compute matchings that behave well with respect to these ranks. There are several notions of optimality here and we have already studied the following: popularity, least unpopularity factor, popularity restricted to maximum cardinality matchings. Our goal is to explore these notions further, for instance, larger cardinality weakly stable matchings and so on.

Some of the work done in natural algorithms as a part of IMPECS includes a mathematical proof that physarum (a slime mold) can compute shortest paths between two sources of food. We are open to pursuing other problems in the field of ``natural algorithms'': these are algorithms developed by evolution over millions of years. Questions in hypergraph colouring, datastructures, and streaming will be studied through the application of combinatorial and information theoretic methods.


No events


  • The deadline for applying for student exchange is March 30, 2015. Students enrolled in a Ph.D. programme at any Indian…
Copyright © 2017 Joomla! demo site. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.