|| Research Interests |||Publications |||Students Advised |||Professional Activities |||Contact ||
| Venkatesh Raman
Theoretical Computer Science
Institute of Mathematical Sciences
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.
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.
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)
|Address (Home)||Plot 3 and 4, Gomathinagar,
Ramnagar 8th Street ,
Ramnagar North Extension,
Chennai 600 042. India.
|Telephone (IMSc)||(044) 2254 1856, 2254 3220|
|Telephone (Home)||(044) 2259 0374|
|FAX (IMSc)||(044) 2254 1586|