Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), Vol 294, No.4, pp.1-16, Jun 2024.
- Succinct Data Structure for Graphs with d-Dimensional t-Representation
Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2024), pp.546, Mar 2024.
- A faster algorithm for Vertex Cover parameterized by solution size
David Harris, Narayanaswamy N S, Appeared in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Mar 2024.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Information and Computation, Vol 105124, Jan 2024. A preliminary version appeared in Data Compression Conference (DCC 2022), Mar 2022.
- Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Manas Jyothi Kashyap, Narayanaswamy N S, Meghana Nasre, Sai Mohith Potluri, Appeared in Algorithmica, Vol 85, No.4, pp.854--878, Jan 2023.
- Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, Narayanaswamy N S, Nisha K K, Vijayaraghunathan Ramamoorthi, Appeared in WALCOM, Mar 2022.
- Budgeted Dominating Sets in Uncertain Graphs
Narayanaswamy N S, David Peleg, Vijayaraghunathan Ramamoorthi, Keerti Choudhary, Avi Cohen, Appeared in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2021.
- The Connected Domination Number of Grids
Narayanaswamy N S, Adarsh Srinivasan, Appeared in 7th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2021), Feb 2021.
- Perfect resolution for Conflict-Free Colouring of Interval Hypergraphs
Dhannya S.M., Narayanaswamy N S, Appeared in The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Mar 2020.
- Fully Dynamic Data Structures for Interval Coloring
Girish Raguvir, Manas Jyothi Kashyap, Narayanaswamy N S, Appeared in 25th International Computing and Combinatorics Conference (COCOON 2019), Aug 2019.
- Minimum Membership Hitting Sets of Axis Parallel Segments
Narayanaswamy N S, Dhannya S.M., Ramya C., Appeared in The 24th International Computing and Combinatorics Conference (COCOON 2018), LNCS, Jul 2018.
- Facility location on planar graphs with unreliable links
Narayanaswamy N S, Meghana Nasre, Vijayaraghunathan Ramamoorthi, Appeared in The 13th International Computer Science Symposium in Russia, Jun 2018.
- Hitting Set for hypergraphs of low VC-dimension
Karl Bringmann, Laszlo Kozma, Shay Moran, Narayanaswamy N S, Appeared in ESA, European Symposium on Algorithms, Sep 2016.
- A Refined Analysis of Online Path Coloring in Trees
Astha Chauhan, Narayanaswamy N S, Appeared in Workshop on Approximation and Online Algorithms, Aug 2016.
- On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, Narayanaswamy N S, Sebastian Ordyniak, Rahul C.S., M S Ramanujan, Appeared in 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2016.
- Approximation and Exact Algorithms for special cases of Connected f-Factors
Narayanaswamy N S, Rahul C.S., Appeared in 10th International Computer Science Symposium in Russia, Jul 2015.
- Block Sorting is APX-Hard
Narayanaswamy N S, Swapneel Roy, Appeared in The 9th International Conference on Algorithms and Complexity, May 2015.
- Block Sorting is APX-Hard
Narayanaswamy N S, Swapnoneel Roy, Appeared in International Conference on Algorithms and Complexity 2015, Feb 2015.
- Approximate Distance Oracle in O(n^2) Time and O(n) Space for Chordal Graphs
Gaurav Singh, Narayanaswamy N S, Ramakrishna G., Appeared in Workshop on Algorithms and Computation, Feb 2015.
- Tree Path Labeling of Hypergraphs – A Generalization of the Consecutive Ones Property
Narayanaswamy N S, Anju Srinivasan, Appeared in Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015), Feb 2015.
- On Minimum Average Stretch Spanning Trees in Polygonal 2-trees
Narayanaswamy N S, Ramakrishna G., Appeared in Accepted at Theoretical Computer Scince 2014, Nov 2014.
- Tree t-spanners in Outerplanar Graphs via Supply Demand Partition
Narayanaswamy N S, Ramakrishna G., Appeared in Accepted at Discrete Applied Mathematics 2014, Oct 2014.
- LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
Samuel Fiorini, Krithika Ramaswamy, Narayanaswamy N S, Venkatesh Raman, Appeared in 22nd European Symposium on Algorithms, Sep 2014.
- Connected f-Factors of Large Minimum Degree in Polynomial Time.
Narayanaswamy N S, Rahul C.S., Appeared in 9th International Colloquium on Graph Theory and Combinatorics (ICGT 2014), Jul 2014.
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
Narayanaswamy N S, Anup Joshi, Appeared in Accepted at 14th Scandinavian Symposium and Workshops on Algorithm Theory(SWAT 2014) - Copenhagen, Denmark, Jul 2014.