Somnath Sikdar

photo
Email sikdar AT cs (dot) rwth-aachen (dot) de
Phone (+49) 241 8021132
Office Address Theoretical Computer Science
Ahornstraße 55, 52074 Aachen, Germany
Office no. 4105b
Postal Address Theoretical Computer Science
Department of Computer Science
RWTH Aachen University
52056 Aachen, Germany

I am a post-doctoral researcher in the theoretical computer science group at RWTH Aachen University. My research focuses on algorithms for graph optimization problems. The algorithm design paradigms that I'm particularly interested include fixed-parameter, approximation and exact algorithms. A recurrent topic in graph optimization problems is designing algorithms for problems that are otherwise intractable on classes of sparse graphs, since sparse graphs often provide sufficient structural footholds for designing efficient algorithms. Sparsity is a rather general concept and the graph classes that I worked with include planar graphs; H-topological-minor-free graphs; graphs of bounded expansion; and no-where dense graphs.

I'm interested in probabilistic graph models of complex networks and algorithmic problems on such networks. Some of the projects on complex networks that I'm working on now are: (overlapping) community detection; motif-finding. Moreover I'm interested in the structure of complex networks. Here is a paper that tries to find structural connections between complex networks and graphs of bounded expansion.

The algorithm for overlapping community detection that we are currently working on uses random walks on graphs simulated by an absorbing Markov chain to detect overlapping communities. This seems promising at least for simulated graphs. The details of this algorithm are in the following paper:

We are planning to test this algorithm on large simulated and real-world instances.

I'm also interested in field of chemo-informatics. This is a nascent field at the intersection of chemistry and computer science and deals with topics such as studying chemical systems using graph grammars; or discovering new drugs using novel search techniques. While I do not actively work in this area, I try to follow developments in this area.

Please note that I do not offer summer internships and I do not reply to such mails.

Back to the Theory Homepage.