Parameterized and Exact Computation
On the Parameterized Complexity of Reconfiguration Problems
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour and Akira Suzuki
Proceedings of IPEC 2013.
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.
LP can be a cure for parameterized problems
N. S. Narayanaswamy, V. Raman, M.S. Ramanujan and S. Saurabh
accepted in STACS 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
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.
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.