N. Narayanaswamy

activity

20092023

most citedFaster Parameterized Algorithms using Linear Programming

19 citations · 31 across the 26 of their papers we have counts for

collaborators

Showing 2011Show all

2 papers · 1 filter

cs.DM2011

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

N. S. Narayanaswamy, N. Sadagopan

We show that minimum connected $(s, t)$ -vertex separator ( $(s, t)$ -CVS) is $Ω (l o g^{2 - ε} n)$ -hard for any $ε > 0$ unless NP has quasi-polynomial Las-Vegas algorithms. i.e., for any $ε > 0$ …

cs.CC2011

On Approximability of Block Sorting

N. S. Narayanaswamy, Swapnoneel Roy

Block Sorting is a well studied problem, motivated by its applications in Optical Character Recognition (OCR), and Computational Biology. Block Sorting has been shown to be NP-Hard…

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

On Approximability of Block Sorting

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