Venkatesh Raman
Professor
Theoretical Computer Science
2254 3220
vraman @ imsc . res . in
220 New Building
Research Interests:
- Parameterized Complexity, Exact Exponential Algorithms, Graph Algorithms
- Space Efficient Data Structures, String Matching
- Sorting and Selection Problems
- Satisfiability
Education:
- MSc (Mathematics) IIT Kanpur 1984
- MMath (Combinatorics and Optimization) University of Waterloo, Canada 1986
- PhD (Computer Science) University of Waterloo, Canada 1991
Career History:
- Post doctoral fellow at University of Waterloo from Feb 1991 to July 1991
- Faculty at IMSc Chennai since July 1991
Courses Taught:
- Data Structures and Algorithms, Parameterized Complexity, Randomized Algorithms
- Advanced Data Structures, Advanced Algorithms
Selected publications:
(Full list can be obtained from DBLP)
Approximability of Clique Transversal in Perfect Graphs (with S. Fiorini, R. Krithika and N. S. Narayanswamy) in Algorithmica (2017).
- On the Parameterized Complexity of Reconfiguration Problems (with Amer Mouawad, Naomi Nishimura, Narges Seymour and Akira Suzuki). Algorithmica 78(1): 274-297 (2017)
- Biconnectivity, Chain Decomposition and s-t numbering using O(n) bits (with Sankardeep Chakraborty and Srinivasa Rao Satti), Proceedings of ISAAC 2016.
- Finding median in read-only memory for integer input (with Timothy Chan and J. Ian Munro), Theoretical Computer Science 2015
- Shortest Reconfiguration Paths in the Solution space of Boolean formulas (with Amer Mouawad, Naomi Nishimura and Vinayak Path) to appear in SIAM Journal on Discrete Mathematics 2017 (preliminary version in ICALP 2015)
- Kernels for Structural Parameterizations of Vertex Cover -- case of small degree modulators (with Diptapriyo Majumdar and Saket Saurabh), IPEC 2015
- Sorting and Selection with Equality Comparisons (with Varunkumar Jayapaul, Ian Munro and Srinvasa Rao Satti), Proceedings of WADS 2015.
- Fixed-parameter tractability of satisfying beyond the number of variables (with Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo), Algorithmica 2014.
- Selection and Sorting in the "Restore" model (with Timothy Chan and Ian Munro) to appear in Transactions on Algorithms 2018, preliminary version in SODA 2014.