research

Theoretical Computer Science

Graph Theory and Combinatorics

Artificial Intelligence

Approximability of Clique Transversal in Perfect Graphs.

Samuel Fiorini, R. Krithika, N.S. Narayanaswamy and Venkatesh Raman.

Accepted at Algorithmica 2017.

Approximation Algorithms for Connected Graph Factors of Minimum Weight.

Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul, Marten Waanders

Accepted at Theory of Computing Systems 2016.

On the Complexity of Connected (s, t)-Vertex Separator.

N.S.Narayanaswamy and N.Sadagopan

Accepted at Journal of Graph Algorithms and Applications 2015.

On Minimum Average Stretch Spanning Trees in Polygonal 2-trees.

N.S Narayanaswamy, G Ramakrishna

Accepted at Theoretical Computer Scince 2014.

Tree t-spanners in Outerplanar Graphs via Supply Demand Partition

N. S. Narayanaswamy, G. Ramakrishna

CoRR abs/1210.7919 (2012) Accepted at Discrete Applied Mathematics 2014.

Obtaining Matrices with the Consecutive Ones Property by Row Deletions.

N.S. Narayanaswamy and R. Subashini

Accepted at Algorithmica 2014.

Characterization of Minimum Cycle Basis in Weighted Partial 2-trees.

N. S. Narayanaswamy and G. Ramakrishna

Accepted at Discrete Applied Mathematics 2014, CoRR abs/1302.5889 (2013).

Faster Parameterized Algorithms using Linear Programming.

Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh

ACM Transactions on Algorithms (TALG), Volume 11 Issue 2, October 2014, (Accepted in 2013)

Another Disjoint Compression Algorithm for OCT.

R. Krithika and N. S. Narayanaswamy

Information Processing Letters, Volume 113 Issue 22-24, November, 2013, Pages 849-851.

Solving minones-2-sat as fast as vertex cover.

Neeldhara Misra, N.S. Narayanaswamy, Venkatesh Raman, Bal Sri Shankar

Theoretical Computer Science, Volume 506, 30 September 2013, Pages 115–121.

A Dirac-type Characterization of k-chordal Graphs.

R. Krithika, Rogers Mathew, N. S. Narayanaswamy, N. Sadagopan

Discrete Mathematics, Volume 313, Issue 24, 28 December 2013, Pages 2865–2867.

Parameterized Algorithms for (r,l)-partization.

R. Krithika and N.S. Narayanaswamy

Journal of Graph Algorithms and Applications 17(2): 129-146 2013 .

A Unified Framework for Bi(Tri)connectivity and Chordal Augmentation.

N.S. Narayanaswamy and N. Sadagopan.

International Journal of Foundations of Computer Science Vol. 24, No. 1 (2013) 67–93 .

Hardness of Subgraph and Supergraph Problems on c-Tournaments.

S. Kanthi Kiran and N.S. Narayanaswamy.

Theoretical Computer Science 412(35): 4629-4635 (2011) .

Dominating Set Based Exact Algorithms for 3-coloring.

N.S. Narayanaswamy and C.R. Subramanian.

Information Processing Letters 111(6): 251-255 (2011) .

A New Characterization of Matrices with the Consecutive Ones Property.

N.S. Narayanaswamy and R. Subhashini.

Discrete Applied Mathematics, Volume 157, Issue 18, November 2009, Pages 3721-3727 .

On the Structure of Contractible Edges in k-connected Partial k-trees.

N.S. Narayanaswamy, N. Sadagopan, and L. Sunil Chandran.

Graphs and Combinatorics, Volume 25, Number 4, November 2009, Pages 557-569 .

On the Structure of Contractible Vertex Pairs in Chordal Graphs.

N.S. Narayanaswamy and N. Sadagopan.

Electronic Notes in Discrete Mathematics, Volume 33, 1 April 2009, Pages 29-36. (Selected papers from International Conference on Graph Theory and its Applications)

A Note on First-Fit Coloring of Interval Graphs.

N.S. Narayanaswamy, R. Subhash Babu.

Order, 25:49-53(2008).

Analysis of Online Algorithms for the Dynamic Convoy Movement Problem.

Ram Gopalan, N.S. Narayanaswamy.

Journal of the Operational Research Society (2009) 60, 1230–1236;
Published online 6 August 2008.

A note on the Hadwiger number of Circular Arc Graphs.

N. S. Narayanaswamy, N. Belkale, L. Sunil Chandran, Naveen Sivadasan.

Information Processing
Letters, 104(1): 10-13 (2007) .

Cuts and Connectivity in Chordal Graphs.

L. Sunil Chandran, N.S. Narayanaswamy.

Ars Combinatoria, 92: 11-19 July 2009 (Accepted in 2006) .

Improved Algorithms for Online Interval Coloring with Bandwidths.

Yossi Azar, Amos Fiat, Meital Levy, N.S. Narayanaswamy.

Theoretical Computer Science, 363(1): 18-27 (2006) .

Protein similarity Search under mRNA structural constraints: application to selenocysteine
incorporation.

Rolf Backofen, N.S. Narayanaswamy, Firas Swidan.

In Silico Biology 2:26 (2002).

Lower Bounds for OBDDs and Nisan’s pseudorandom generator.

N.S. Narayanaswamy, C.E. Veni Madhavan.

Electronic Colloquium on Computational Complexity
(ECCC) 8(20): (2001).

A Refined Analysis of Online Path Coloring in Trees

Astha Chauhan, N.S. Narayanaswamy.

Accepted at WAOA 2016.

On the Complexity Landscape of Connected f-factor Problems

Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul and Ramanujan M. S.

Accepted at MFCS 2016.

Hitting Set for hypergraphs of low VC-dimension

Karl Bringmann, László Kozma, Shay Moran and N.S. Narayanaswamy.

Accepted at ESA 2016.

Approximation and Exact Algorithms for special cases of Connected $f$-Factors.

N.S. Narayanaswamy and Rahul C.S.

Accepted at CSR 2015.

Block Sorting is APX-Hard.

N.S. Narayanaswamy and Swapnoneel Roy.

Accepted at CIAC 2015.

Approximate Distance Oracle in $O(n^2)$ Time and $O(n)$ Space for Chordal Graphs.

Gaurav Singh, N.S. Narayanaswamy and G. Ramakrishna.

Accepted at WALCOM 2015.

Tree Path Labeling of Hypergraphs – A Generalization of the Consecutive Ones Property.

N.S. Narayanaswamy and Anju Srinivasan.

Accepted at CALDAM 2015.

LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs.

Samuel Fiorini, R. Krithika, N.S. Narayanaswamy and Venkatesh Raman.

Accepted at ESA 2014.

Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments.

N.S. Narayanaswamy and Anup Joshi.

Accepted at SWAT 2014.

Connected f-Factors of Large Minimum Degree in Polynomial Time.

N.S. Narayanaswamy and C.S. Rahul.

Accepted at ICGT 2014.

On Minimum Average Stretch Spanning Trees in Polygonal 2-trees.

N.S. Narayanaswamy and G. Ramakrishna.

Accepted at WALCOM 2014.

Approximability of Connected Factors.

Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N.S. Narayanaswamy and C.S.Rahul.

Accepted at WAOA 2013.

FPT algorithms for Consecutive Ones Submatrix problems.

N.S. Narayanaswamy and R. Subashini.

Accepted at IPEC 2013.

Characterization of Minimum Cycle Basis in Weighted Partial 2-trees.

N.S. Narayanaswamy and G Ramakrishna.

Proceedings of CTW 2012, 193-196.

LP can be a cure for Parameterized Problems.

N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, Saket Saurabh.

Accepted at STACS 2012.

Generalized Above Guarantee Vertex Cover and r-Partization.

N.S. Narayanaswamy and R. Krithika.

Accepted at Workshop on Algorithms and Computation (WALCOM 2012) 2012.

Planning for the Convoy Movement Problem.

Anand Kumar, Deepak Khemani, I. Murugeswari, N.S. Narayanaswamy.

Accepted at International Conference on Agents and Artificial Intelligence (ICAART 2012) 2012.

A Novel Data Structure for Biconnectivity, Triconnectivity, and k-tree Augmentation.

N.S. Narayanaswamy and N. Sadagopan.

In Proc. Computing: The Australasian Theory Symposium (CATS 2011), Perth, Australia 2011. ACS, CRPIT 119: 45-54.

A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs.

Esha Ghosh, N.S. Narayanaswamy and C. Pandu Rangan.

Workshop on Algorithms and Computation, (WALCOM 2011), New Delhi, India, 2011. Springer Verlag, LNCS 6552: 191-201.

Solving minones-2-sat as Fast as vertex cover.

Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, Bal Sri Shankar.

In the Proceedings of Mathematical Foundations of Computer Science, MFCS 2010: 549-555.

TRANS: Schema-Aware Mapping of OWL Ontologies into Relational Databases.

Saurabh Kejriwal and N. S. Narayanaswamy.

In the 15th International Conference on Management of Data (COMAD 2009), December 9-12, 2009, Mysore, India.

Tuning Search Heuristics for Classical Planning with Macro Actions.

I. Murugeswari, N. S. Narayanaswamy.

In the 22nd International FLAIRS Conferences, May 19-22nd, 2009, Florida.

Algorithms and heuristics for the single machine completion time variance minimization problem.

B. Chaitanya, N.S. Narayanaswamy, B. Srirangacharyalu, G. Srinivasan.

In the 40th Annual Convention of OR Society of India, Indian National Science Academy, New Delhi, December
04-06, 2007.

k-tree characterizing sequences.

Zvi Lotker, Debapriyo Majumdar, N.S. Narayanaswamy, Ingmar Weber.

In Proceedings of
COCOON, Taipei, Taiwan, August 15-18, 2006, LNCS 4112,
Springer 2006.

On the Arrangement of Cliques in Chordal Graphs with Respect to Cuts.

L.Sunil Chandran, N.S. Narayanaswamy.

In Proceedings of COCOON, Jeiju Island, South
Korea, August 17-20, 2004, pp. 274-286, LNCS
3106, Springer 2004.

Dynamic Storage Allocation and Online Colouring Interval Graphs.

N.S. Narayanaswamy.

In Proceedings of COCOON, Jeiju Island, South Korea, August 17-
20, 2004, pp. 274-286, LNCS 3106, Springer 2004.
Invited for presentation at Workshop on Online Algorithms, 2004, Copenhagen.

Algorithms for Satisfiability using Independent Sets of Variables.

Ravi Gummadi, N.S. Narayanaswamy, R. Venkatakrishnan.

In Proceedings of SAT, Vancouver,
Canada, May 10-13, 2004, LNCS, Springer 2004.

An Optimal Lower Bound for Resolution with 2-Conjunctions.

Jan Johannsen, N.S. Narayanaswamy.

In Proceedings of MFCS, Warsaw, Poland, August
26-30, 2002, pp 387-398, LNCS 2420, Springer 2002.

On the Complexity of Protein Similarity Search under mRNA Structural Constraints.

Rolf Backofen, N.S. Narayanaswamy, Firas Swidan.

In Proceedings of STACS, Juan Les Pins,
France, March 14-16, 2002, pp. 274-286, LNCS 2285, Springer
2002.

Protein similarity Search under mRNA structural constraints: application to selenocysteine
incorporation.

Rolf Backofen, N.S. Narayanaswamy, Firas Swidan.

In Proceedings of the German Conference
on Bioinformatics, Braunschweig, October 7-10, 2001, pp. 135-140.

On Assigning Prefix Free Codes to the Vertices of a Graph.

N.S. Narayanaswamy, C.E. Veni Madhavan.

In Proceedings of COCOON, Guilin, China,
August 20-23, 2001, pp. 328-337, LNCS 2108, Springer 2001.

Graph Editing to Bipartite Interval Graphs: Exact and Asymptotic Bounds.

K. Cirino, S. Muthukrishnan, N.S. Narayanaswamy, H. Ramesh

In Proceeding of FSTTCS,
Karaghpur, India, December 18-20, 1997, pp. 37-53, LNCS
1346, Springer 1997.

- N. Sadagopan (IITM M.S, IITM PhD, Assistant Professor at IIIT-D&M)
- Rakesh Mohanty (IITM PhD, Reader at Burla University)
- G. Ramakrishna (IITM M.S, IITM PhD, Assistant Professor at IIIT-Sri City)
- R. Subashini (IITM M.Tech, IITM PhD, Assistant Professor, NIT Calicut)
- R. Krithika (IITM M.S, IITM PhD(Aug 2016), Assistant Professor, IIT Palakkad)
- C.S. Rahul (IITM M.Tech(with Prof. Hema Murthy), IITM PhD(Nov 2016), Assistant Professor, BITS Dubai)
- Dhannya Gopakumar (IITM PhD(Sep 2020), Now with NPTEL)
- Vijaya Ragunathan (Current Phd, co-guiding with Meghana Nasre)
- Manas Jyoti Kashyop (IITM M.Tech, Current PhD (Aug 2016))
- Rajesh Pandian (IITM M.Tech, Current PhD (Aug 2016))
- Anil Kumar (Current PhD (September 2016))
- K.K. Nisha (Current PhD (August 2017))
- Girish Balakrishnan (Current PhD (August 2019))
- R. Subhash Babu (IITM M.S, D.E. Shaw)
- Srinibas Swain (IITM M.S, Oracle)
- Bhanu Kovuri (IITM M.S, Oracle)
- Saurabh Kejriwal (IITM M.S, Oracle)
- Apoorve Dubey (IITM M.S)
- Swapnoneel Roy (IITM M.S, PhD(SUNY Buffalo), Univ of North Florida)
- Anju Srinivasan (IITM M.S)
- Anup Joshi (IITM M.S, Now PhD student at Dartmouth)
- Gaurav Singh (IITM M.S, VMWare)
- Aastha Chauhan (IITM M.S, Robert Bosch Limited)
- Sharmili Murthy (Current M.S, Microsoft Limited)

research.txt · Last modified: 2021/08/18 10:51 by admin