Venkatesh Raman
Theoretical Computer Science
Institute of Mathematical Sciences

Research Interests

Parameterized Complexity
Succinct (Space Efficient) Data Structures
Approximate Algorithms
Sorting, Selection and related problems

[Back to top]

Publications

Proceedings Edited

Proceedings of the 19th FST and TCS Conference
C Pandu Rangan, V. Raman and R Ramanujam
Springer Verlag LNCS 1738

Lecture Notes

Some introductory notes on Algorithm Design and Analysis [pdf]

Selected Publications in Data Structures, Parameterized and Exact Computation and Selection, Sorting and others.

[Back to top]

Parameterized and Exact Computation

On the Directed degree-preserving spanning tree problem,
D. Lokshtnov, V. Raman, S. Saurabh and S. Sikdar,
Proceedings of IWPEC 2009, to appear.

The Budgeted Unique Coverage Problem and Color-Coding,
N. Mishra, V. Raman, S. Saurabh and S. Sikdar, 
Proceedings of the 4th International Computer Science Symposium in Russia (CSR) 2009.

Solving Dominating Set in Larger Class of Graphs -- FPT algorithms and Polynomial Kernels,
G. Philip, V. Raman, S. Sikdar
Proceedings of the ESA 2009 to appear.

Konig Deletion Sets and Vertex Covers Above the Matching Size
S. Mishra, V. Raman, S. Saurabh and S. Sikdar
Proceedings of the ISAAC 08, Springer LNCS 5369, 836-847.

Parameterizing Algorithms for Generalized Domination,
V. Raman, S. Saurabh, S. Srihari,
Proceedings of COCOA 2008, Springer LNCS 5165, pages 116-126.

Parameterized Complexity of the Induced Subgraph problem in directed graphs [pdf]
V. Raman and S. Sikdar, Information Processing Letters 104 (2007) 79-85

Improved FPT algorithms for two edge problems --MaxCut and MaxDag [pdf]
V. Raman and S. Saurabh, Information Processing Letters 104 (2007) 65-72

The Complexity of Finding Subgraphs whose matching number equals the vertex
cover number, 
S. Mishra, V. Raman, S. Saurabh, S. Sikdar, C. R. Subramanian,
Proceedings of the 18th International Symposium on Algorithms and Computation
(ISAAC 2007), Springer LNCS 4835, 268-279.

Parameterized Complexity of the Unique Coverage Problem, 
H. Moses, V. Raman and S. Sikdar, 
Proceedings of the 18th International Symposium on Algorithms and Computation
(ISAAC 2007), Springer LNCS 4835, pages 621-631.

Exact and Parameterized Algorithms through (old and new) Structural Graph theoretical Results
V. Raman and S. Saurabh
In the proceedings of the International Conference on Discrete Mathematics (2006), Pages 177-189.

Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
[pdf]
S. Gupta, V. Raman and S. Saurabh
26th Conference on Foundations of Software Technology and Theoretical 
Computer Science (FSTTCS 2006).Kolkata, India, December 13-15, 2006. 

Parameterizing above or below guaranteed values 
M. Mahajan and V. Raman and S. Sikdar
Journal of Computer and System Sciences 75(2):137-153 (2009).
(Preliminary version as 'Parameterizing MAXSNP problems above Guaranteed Values' [pdf]
 in
Proceedings of 2nd International Workshop on Parameterized and Exact Computation IWPEC'06, 13 - 15 Sep, 2006, Zuerich (Switzerland). (part of ALGO 2006) .
Springer-Verlag Lecture Notes in Computer Science series Volume 4169 pp 38--49.)

Short Cycles make W-hard problems hard; FPT algorithms for W-hard problems in 
Graphs with no short cycles [pdf]
V. Raman and S. Saurabh
Algorithmica 52(2):203-225 (2008).
(Preliminary version as `Triangles, 4-Cycles and Parameterized (In-) 
Tractability in the proceedings of  10th Scandinavian Workshop on Algorithmic 
Theory SWAT, LNCS  4051, 304-315 (2006).)

Faster Fixed Parameter Tractable Algorithms for Finding Feedback Vertex Sets [pdf]
V. Raman, S. Saurabh and C. R. Subramanian
ACM Transactions on Algorithms (TALG) 2 (3) 403-415 (July 2006). 
(Preliminary versions in ISAAC 2002 and GRACO 2004).

Parameterized Algorithms for Feedback Set Problems and Their Duals in
Tournaments [pdf]
V. Raman and S. Saurabh
Theoretical Computer Science (TCS).  Volume 351, Issue 3, Pages  446-458 (2006)
(Invited Paper of Ist International Workshop on Parameterized and Exact Computation)

Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques [ps]
V. Raman ,  S. Saurabh and S.Sikdar     
in `Theory of Computing Systems' 41(30:563-587 (2007).
(Preliminary version of the paper appeared as 'Improved Exact Exponential 
Algorithms for Vertex Bipartization and Other Problems'[pdf] 
In the proccedings of  9th Italian Conferenece on Theoretical Computer Science, ICTCS,  LNCS 3701, 375-389 (2005))

Parameterized Complexity of Finding Hereditary Properties 
S. Khot and V. Raman.
Theoretical Computer Science 289 (2002) 997-1008.

Approximation Algorithms for some Parameterized Counting Problems [pdf]
V. Arvind and V. Raman.
Electronic Colloquium on Computational Complexity, 31 (2002). 
Proceedings of ISAAC 2002 Springer LNCS 2518 453-464.

The Complexity of irredundant sets parameterized by size [pdf]
R. G. Downey, M. R. Fellows and V. Raman.
Discrete Applied Mathematics 100 (2000) 155-167.

Upper Bounds for MaxSat: Further Improved [ps]
N. Bansal and V. Raman.
Proceedings of ISAAC 99 (Springer LNCS 1741) 247-258.

Parameterizing Above the Guarantee: MAXSAT and MAXCUT [ps]
M. Mahajan and V. Raman.
Journal of Algorithms 31 (1999) 335-354.
 
A Simplified NP-Complete MAXSAT Problem [pdf]
V. Raman, B. Ravikumar and S. Srinivasa Rao.
Information Processing Letters 65 (1998) 1-6.

An Improved Fixed Parameter Algorithm for Vertex Cover 
R. Balasubramanian, M. Fellows and V. Raman.
Information Processing Letters, 65 (1998) 163 -168

Parameterized Complexity 
V. Raman.
in Proceedings of the 7th National Seminar on Theoretical Computer Science, June 1997, (Chennai, India) I-1 to I-18.

[Back to top].

Data Structures

Succinct ordinal trees with level-ancestor queries [pdf]
R. F. Geary, R. Raman and V. Raman 
ACM Transactions on Algorithms 2 (2006), pp. 510-534.
SODA '04 special issue, J. I. Munro and A. Lopez-Ortiz, eds.

A simple optimal representation for balanced parentheses [pdf]
R. F. Geary, N. Rahman, R. Raman and V. Raman 
Theoretical Computer Science 368 (2006), pp. 231-246.
CPM '04 special issue, U. Dogrusoz, S. Muthukrishnan and S. C. Sahinalp, eds.

Representing trees of higher degree [pdf]
D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman and S. S. Rao
Algorithmica, 43 (2005), pp. 275-292.

Succinct Representations of Permutations [pdf]
J.I. Munro, R. Raman, V. Raman, S. S. Rao.
Proceedings of ICALP 2003 (Springer LNCS 2719, 345-.)

Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multisets [pdf]
Rajeev Raman, V. Raman and S. Srinivasa Rao.
Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2002.
Journal version, in ACM Transactions on Algorithms 3(4) (2007).

Representing Dynamic Trees Succinctly 
J. I. Munro, V. Raman and Adam Storm.
Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2001.

A tradeoff between search and update in dictionaries 
J. Radhakrishnan and V. Raman.
Information Processing Letter 80 (2001) 243-247.

Succinct Dynamic Data Structures [pdf]
R. Raman, V. Raman, S. S. Rao
Proceedings of WADS 2001.

Explicit Deterministic Construction for Membership in the Bitprobe Model [pdf]
J. Radhakrishnan, V. Raman and S. S. Rao
Proceedings of ESA 2001.

Space Efficient Suffix Trees [pdf]
J.I. Munro, V. Raman and S. Srinivasa Rao.
Journal of Algorithms 39 (2) (2001) 205-222.

Succinct Representation of Balanced Parentheses and Static Trees 
J. I. Munro and V. Raman.
1997 IEEE Symposium on Foundations of Computer Science: 118-126
SIAM J. Computing, Vol. 31, No.3 (2001) 762-776.

Static Dictionaries Supporting Rank [pdf]
V. Raman and S. S. Rao.
Proceedings of ISAAC 99 (Springer LNCS 1741) 18-26.

Path Balance Heuristic for Self-Adjusting Binary Search Trees
R. Balasubramanian and Venkatesh Raman
FSTTCS 1995: 338-348.

[Back to top]

Selection, Sorting and Others

Approximate Block Sorting [ps]
M. Mahajan and R. Rama and V. Raman and S. Vijayakumar.
International Journal of Foundations of Computer Science
Volume 17(2) (April 2006), pp. 337--355.

On the pseudoachromatic number of join of graphs
R Balasubramanian, V. Raman V. Yegnanarayanan
International Journal of Computer Mathematics
Vol 80 No. 9 pages 1131-1137 (Sept 2003)

Improved Upper Bounds for Time-Space Tradeoffs for Selection 
V. Raman and S. Ramnath.
Nordic Journal of Computing 6 (1999) 162-180.

Selecting small ranks in EREW PRAM 
S. Ramnath and V. Raman.
Information Processing Letters 71 (1999) 183-186.

Finding Generalized Hamiltonian paths in Tournaments
Proceedings of the conference on Graph Connections(1999)

Finding Scores in Tournaments 
R. Balasubramanian, V. Raman and G. Srinivasaraghavan.
Journal of Algorithms 24 (1997) 380-394.

Selection from Read-Only Memory and Sorting with minimum Data Movement 
J. I. Munro and V. Raman.
Theoretical Computer Science 165 (1996) 311-323.

Fast Stable In-Place Sorting with O(n) Data Moves
J. I. Munro and Venkatesh Raman
Algorithmica 16(2):151-160 (1996).

Sorting Multisets and Vectors In-Place
J. I. Munro and Venkatesh Raman
WADS 1991: 473-480.

Stable in situ sorting and minimum data movement 
J. I. Munro, V. Raman, J.S. Salowe
BIT 30(1990) 220-234

Sorting with Minimum Data Movement
J. I. Munro and V. Raman
Journal of Algorithms 13(3) (1992)

[Back to top]

Students Advised

PhD Students
S Srinivasa Rao
Thesis : Succinct Data Structures (2002)

Saket Saurabh
Thesis: Exact Algorithms for Optimization and Parameterized Versions of some graph theoretic problems (2008)

Somnath Sikdar
Thesis: Parameterizing from the extremes -- feasible parameterizations of some NP hard Optimization Problems (submitted July 2009)

Geevarghese Philip

Neeldhara Misra

Master's Students
S V Nagaraj
Thesis : Optimal Binary Search Trees
April 1994

S Srinivasa Rao
Thesis : A survey of Approximation Algorithms for the Maximum Satisfiability Problem
April 1997

G Srinivasan (Anna University)
Thesis : Self Adjusting Binary Search Trees
May 1998

V Reemus Kumar (Madurai Kamaraj University)
Thesis : Implicit Data Structures for Multikey Search Problem and implementing Rank and Select in a Bit vector
May 2002

R Ramani (REC Trichy)
Thesis : Implementation of Rank and Select and other succinct strutures
June 2003

[Back to top]

Professional Activities

Member of IWPEC steering committee
PC member of TAMC 2009
PC member of CATS 2010
Program Committee member of IWPEC 2006 conference
Principal Investigator, DST-DAAD (Indo-German) project on 'Provably efficient exact algorithms for computationally hard problems' 2005-2007
Member, DST-DAAD (Indo-German) project in 'Algorithmic and Complexity Issues in Fixed Parameter (In)Tractability'
Prinicipal Investigator, Indo-UK project on 'Highly Efficient Data Structures'
Program Committee Co-chair of the FST & TCS 1999 Conference
Member of the council of Indian Association for Research in Computing Science (IARCS) 2002-2005
Program Committee member of TCS 2002 conference held in Montreal, Canada in August 2002
Program Committee member of the FST &TCS 2002, 1997 and 1996 Conferences
Organizing Committee member of the FST & TCS 1998 Conference

[Back to top]

Personal Information

Address (Home)	Plot 3 and 4, Gomathinagar, Ramnagar 8th Street , Ramnagar North Extension, Velacheri, Chennai 600 042. India.
Telephone (IMSc)	(044) 2254 1856, 2254 3220
Telephone (Home)	(044) 2259 0374
FAX (IMSc)	(044) 2254 1586
E-Mail