Advanced Data Structures Course, Jan 2012

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 5th IPEC (International Symposium on Parameterized and Exact Computation) Symposium
V. Raman and S. Saurabh
Springer Verlag LNCS 6478 (December 2010).

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

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

Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs
Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai and Venkatesh Raman
accepted in SWAT 2012.

Parameterized Algorithms for Even Cycle Transversal
P. Misra, V. Raman, M. S. Ramanujan and S. Saurabh
accepted in WG 2012.

Fixed-parameter tractability of satisfying beyond the number of variables
R. Crowston, G. Gutin, M. Jones, V. Raman, S. Saurabh and A. Yeo 
accepted in SAT 2012.

LP can be a cure for parameterized problems
N. S. Narayanaswamy, V. Raman, M.S. Ramanujan and S. Saurabh
accepted in STACS 2012.

Parameterized Complexity of MaxSat Above Average 
R. Crowston, G. Gutin, M. Jones, V. Raman and S. Saurabh
CORR abs/1108.4501:(2011) accepted in LATIN 2012.

A polynomial kernel for feedback arc set in bipartite tournaments
P. Misra, V. Raman, M. S. Ramanujan, S. Saurabh
accepted in ISAAC 2011.

On Parameterized Independent Feedback Vertex Set
N. Misra, G. Philip, V. Raman and S. Saurabh,
Proceedings of COCOON 2011, 98-109.

Paths, Flowers and Vertex Cover
V. Raman, M. S. Ramanujan and S. Saurabh,
Proceedings of ESA 2011, 382-393.

Bidimensionality and EPTAS [pdf]
F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh,
Proceedings of ACM-SIAM symposium on Discrete Algorithms (SODA) 2011.

The effect of Girth on the Kernalization Complexity of Connected Dominating Set [pdf],
N. Misra, G. Philip, V. Raman and S. Saurabh,
Proceedings of FSTTCS 2010: 96-107.

Lower Bounds for Kernalization [pdf],
N. Misra, V. Raman and S. Saurabh,
Discrete Optimization 8(1): 110-128 (2011).

Fast Local Search Algorithms for Weighted Feedback Arc Set in Tournaments [pdf],
F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh,
in the Proceedings of Conference on Artificial Intelligence (AAAI 2010).

A Quartic Kernel for Pathwidth-One Vertex Deletion [pdf],
G. Philip, V. Raman and Y. Villanger,
in the Proceedings of Graph Theoretic Concepts in Computer Science, WG 2010: 196-207.

Solving Minones 2SAT as fast as Vertex Cover [pdf],
N. Misra, N. Narayanaswamy, V. Raman and Balsri Shankar,
in the proceedings of Mathematical Foundations of Computer Science (MFCS) 2010: 549-555.

Fixed-parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing [pdf],
P. Heggernes, D. Kratsch, D. Lokshtanov, V. Raman and S. Saurabh,
in the proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT) 2010: 334-345.

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs [pdf],
F. Fomin, F. Horn, D. Lokshtanov, V. Raman and S. Saurabh
in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) 2010: 251-262.

FPT Algorithms for Connected Feedback Vertex Set [pdf],
N. Misra, G. Philip, V. Raman, S. Saurabh and S. Sikdar,
in the Proceedings of Workshop on Algorithms and Computation (WALCOM) 2010; 
expanded version in the Journal of Combinatorial Optimization (April 2011) 1-16..

Subexponential Algorithms for Partial Cover Problems [pdf],
F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh,
Information Processing Letters 111(16):814-818 (2011),
preliminary version in the proceedings of FSTTCS 2009 Conference.

The Complexity of Konig Subgraph Problems and Above-Guarantee Vertex Cover [pdf]
S. Mishra, V. Raman, S. Saurabh, S. Sikdar and C. R. Subramanian,
Algorithmica (May 2010).
Preliminary versions appeared in the Proceedings of ISAAC 2007 and ISAAC 2008 symposiums.

On the Directed degree-preserving spanning tree problem [pdf],
D. Lokshtnov, V. Raman, S. Saurabh and S. Sikdar,
Discrete Optimization 8(1): 97-109 (2011),
preliminary version in the Proceedings of IWPEC 2009.

The Budgeted Unique Coverage Problem and Color-Coding [pdf],
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 [pdf],
G. Philip, V. Raman, S. Sikdar
Proceedings of the ESA 2009, expanded version accepted in a journal

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

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 [pdf]
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 Representations of Permutations and Functions
J.I. Munro, R. Raman, V. Raman, S. S. Rao.
Theoretical Computer Science (2012) 74-88.
CoRR abs/1108.4501:(2011)
preliminary version in Proceedings of ICALP 2003 (Springer LNCS 2719, 345-.) [pdf]

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

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)

(the following three jointly supervised with Saket Saurabh)
Somnath Sikdar
Thesis: Parameterizing from the extremes -- feasible parameterizations of some NP hard Optimization Problems (June 2010)

Geevarghese Philip
Thesis: The kernelization complexity of some domination and covering problems (September 2011)

Neeldhara Misra
Thesis: Kernels for the F-Deletion problem (September 2011)

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

Geevarghese Philip
Thesis: Fixed-Parameter Algorithms for Graph Problems Using Graph Minor Theory
April 2008

Neeldhara Misra
Thesis: Infeasibility of Polynomial Kernelization
April 2009

[Back to top]

Professional Activities

Jointly editing (with Saket Saurabh) Algorithmica special issue on parameterized and exact computation
PC member of WALCOM 2012, SPIRE 2011
PC Co-chair of IPEC (formerly IWPEC) 2010
Member of IWPEC steering committee (2006-2010)
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